两名玩家轮流用多堆石子玩游戏。每回合玩家可以选择从一堆石子中移走 1、2、4 或 9 个石子；或者，他们可以选择将包含两个或更多石头的一堆分成两个非空堆。获胜者是移走最后一块石头的玩家。

如果要移动的玩家无法通过最佳玩法迫使获胜，则一堆堆被称为失败位置。将 $S(N,m)$ 定义为由 $m$ 堆石子引起的不同失败位置的数量，其中每堆包含从 $1$ 到 $N$ 的石子。如果两个位置由相同的桩尺寸组成，则认为它们是等效的。也就是说，堆的顺序并不重要。

您将获得 $S(12,4)=204$ 和 $S(124,9)=2259208528408$。

查找 $S(12491249,1249)$。以 $912491249$ 为模给出你的答案。