Двое играют в игру с несколькими кучками камней и ходят по очереди. В каждый ход игрок может убрать 1, 2, 4 или 9 камней из одной кучки, или же разделить одну кучку с двумя или более камнями на две непустые кучки. Выигрывает тот, кто уберет последний камень.

Набор кучек называется проигрышной позицией, если ходящий игрок не может обеспечить себе победу оптимальной стратегией игры. Определим $S(N, m)$ как количество различных проигрышных позиций, которые могут возникнуть из $m$ кучек камней, где каждая кучка содержит от $1$ до $N$ камней. Две позиции считаются эквивалентными, если они состоят из кучек с одинаковыми размерами. Другими словами, порядок кучек не имеет значения.

Известно, что $S(12,4)=204$ и $S(124,9)=2259208528408$.

Найдите $S(12491249,1249)$. В качестве ответа приведите остаток от деления полученного числа на $912491249$.