考虑将 $n$ 硬币排列成一个圆圈，每个硬币都显示正面或反面。一次移动包括翻转 $k$ 个连续硬币：尾-头或头-尾。使用一系列这些动作的目标是让所有硬币都正面朝上。

考虑如下所示的示例，其中 $n=8$ 和 $k=3$，初始状态是一枚硬币，显示出反面（黑色）。该示例显示了此状态的解决方案。

对于给定的 $n$ 和 $k$ 值，并非所有状态都是可解的。 令 $F(n,k)$ 为可解的状态数。已知 $F(3,2)=4$、$F(8,3)=256$ 和 $F(9,3)=128$。

进一步定义： $$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$ 为模给出你的答案。