Alice 和 Bob 轮流玩一个由 $c$ 个不同硬币组成的游戏，棋盘上的大小为 $n$ x $n$。

游戏可以从棋盘上的方格中任意排列 $c$ 硬币开始。任何时候都有可能有不止一枚硬币同时占据棋盘上的同一个方格。硬币是可以区分的，因此交换两个硬币会产生不同的排列，当（且仅当）它们位于不同的方块上时。

在给定的回合中，玩家必须选择一枚硬币并将其向左或向上移动 $2$、$3$、$5$ 或 $7$ 空间。唯一的限制是硬币不能离开棋盘的边缘。

当一名玩家无法做出有效的移动时，游戏结束，从而使另一名玩家获得胜利。

假设爱丽丝先走，并且两位玩家都在最佳状态下玩，让 $M(n,c)$ 为爱丽丝可以确保获胜的可能开始安排的数量，给定一个大小为 $n$ × $n$ 的棋盘，并有 $c$ 不同的硬币。

例如，$M(3,1)=4$、$M(3,2)=40$ 和 $M(9,3)=450304$。

$M(10000019,100)$ 的最后 $9$ 数字是多少？