Алиса и Боб по очереди играют в игру с $c$ различными монетами на шахматной доске размером $n$ на $n$.

Игра может начинаться с любого расположения $c$ монет в клетках доски. В любой момент времени одну и ту же клетку доски могут одновременно занимать больше одной монеты. Все монеты отличаются друг от друга, поэтому, если поменять две монеты местами, общее расположение монет на доске изменится тогда и только тогда, если они находятся на разных клетках.

В свой каждый ход игрок должен выбрать монету и переместить ее вверх или влево на $2$, $3$, $5$ или $7$ клеток. Единственное ограничение состоит в том, что монета не может быть перемещена за пределы доски.

Игра заканчивается, когда игрок больше не может сделать разрешенный ход, таким образом предоставляя победу второму игроку.

Предположив, что Алиса ходит первой и что оба игрока придерживаются оптимальной стратегии, пусть $M(n, c)$ будет количеством возможных начальных расположений, при которых Алиса может обеспечить себе победу, на доске размером $n$ на $n$ с $c$ различными монетами.

Например, $M(3, 1) = 4$, $M(3, 2) = 40$ и $M(9, 3) = 450304$.

Каковы последние $9$ цифр значения $M(10\,000\,019, 100)$?