---

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(\mathrm{mod}1000000007)$.

Find $S({10}^7)$. Give your answer modulo $1000000007$.

---

硬币圈

$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(\mathrm{mod}1000000007)$。

求$S({10}^7)$，并将你的答案对$1000000007$取余。

---