Рассмотрим $n$ монет, расположенных в круг, где каждая монета повернута орлом или решкой. Один ход заключается в переворачивании $k$ последовательно расположенных монет: орел-решка или решка-орел. Задача - используя последовательность ходов, перевернуть все монеты решкой вверх.

Расммотрим пример, показанный ниже, где $n=8$ и $k=3$ и в начальном расположении одна монета повернута решкой (черная). В примере показано решение для такого начального расположения.

Не все начальные расположения имеют решение для данных значений $n$ и $k$. Пусть $F(n,k)$ будет количеством начальных расположений, которые имеют решение. Известно, что $F(3,2) = 4$, $F(8,3) = 256$ и $F(9,3) = 128$.

Далее определим:

Также известно, что $S(3) = 22$, $S(10) = 10444$ и $S(10^3) \equiv 853837042 \pmod{1\,000\,000\,007}$

Найдите $S(10^7)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$