Problem 728

Circle of Coins

Consider $n$ coins arranged in a circle where each coin shows heads or tails. A move consists of turning over $k$ consecutive coins: tail-head or head-tail. Using a sequence of these moves the objective is to get all the coins showing heads.

Consider the example, shown below, where $n=8$ and $k=3$ and the initial state is one coin showing tails (black). The example shows a solution for this state.

For given values of $n$ and $k$ not all states are solvable. Let $F(n,k)$ be the number of states that are solvable. You are given that $F(3,2) = 4$, $F(8,3) = 256$ and $F(9,3) = 128$.

Further define:
$$\displaystyle S(N) = \sum_{n=1}^N\sum_{k=1}^n F(n,k)$$

You are also given that $S(3) = 22$, $S(10) = 10444$ and $S(10^3) \equiv 853837042 \pmod{1\ 000\ 000\ 007}$.

Find $S(10^7)$. Give your answer modulo $1\ 000\ 000\ 007$.

硬币圈

$n$枚硬币摆成一圈，初始状态下硬币任意地正面或反面朝上。每一次行动可以将相邻的$k$枚硬币翻面：正面变为反面，反面变为正面。最终目标是通过一系列行动将所有的硬币翻为正面朝上。

考虑如下所示这个例子，其中$n=8$，$k=3$，初始状态下只有一枚硬币为反面（用黑色表示）。下图展示了其中一种将初始状态变为全正面朝上的解法。

对于给定的$n$和$k$的取值，不是所有的初始状态都能够完成目标。记$F(n,k)$为所有能够完成目标的初始状态数目。已知$F(3,2) = 4$，$F(8,3) = 256$，$F(9,3) = 128$。

进一步地，记
$$\displaystyle S(N) = \sum_{n=1}^N\sum_{k=1}^n F(n,k)$$

已知$S(3) = 22$，$S(10) = 10444$，$S(10^3) \equiv 853837042 \pmod{1\ 000\ 000\ 007}$。

求$S(10^7)$，并将你的答案对$1\ 000\ 000\ 007$取余。