Problem 707

Lights Out

Consider a $w \times h$ grid. A cell is either ON or OFF. When a cell is selected, that cell and all cells connected to that cell by an edge are toggled on-off, off-on. See the diagram for the $3$ cases of selecting a corner cell, an edge cell or central cell in a grid that has all cells on (white).

The goal is to get every cell to be off simultaneously. This is not possible for all starting states. A state is solvable if, by a process of selecting cells, the goal can be achieved.

Let $F (w, h)$ be the number of solvable states for a $w \times h$ grid. You are given $F (1, 2) = 2$ , $F (3, 3) = 512$ , $F (4, 4) = 4096$ and $F (7, 11) \equiv 270016253 (\mod 1 000 000 007)$ .

Let $f_{1} = f_{2} = 1$ and $f_{n} = f_{n - 1} + f_{n - 2}, n \geq 3$ be the Fibonacci sequence and define
$S (w, n) = \sum_{k = 1}^{n} F (w, f_{k})$
You are given $S (3, 3) = 32$ , $S (4, 5) = 1052960$ and $S (5, 7) \equiv 346547294 (\mod 1 000 000 007)$ .

Find $S (199, 199)$ . Give your answer modulo $1 000 000 007$ .

关灯

考虑一个 $w \times h$ 的格阵，其中每一格有开或关两种状态。当某一格被选中时，这一格以及相邻格的状态会发生变化，若原本是开则变为关，若原本是关则变为开。下图展示了原本所有格均为开状态（表示为白色）的格阵在选中了一个角上的格、一个边上的格和一个中间的格后的情景。

从任意起始状态出发，并不是总能够将所有格变为关状态。如果能够做到，则称相应的起始状态为可解的。

记 $F (w, h)$ 为 $w \times h$ 格阵下可解起始状态的数目。已知 $F (1, 2) = 2$ ， $F (3, 3) = 512$ ， $F (4, 4) = 4096$ ， $F (7, 11) \equiv 270016253 (\mod 1 000 000 007)$ 。

考虑斐波那契数列 $f_{1} = f_{2} = 1$ ， $f_{n} = f_{n - 1} + f_{n - 2}, n \geq 3$ ，并记
$S (w, n) = \sum_{k = 1}^{n} F (w, f_{k})$
已知 $S (3, 3) = 32$ ， $S (4, 5) = 1052960$ ， $S (5, 7) \equiv 346547294 (\mod 1 000 000 007)$ 。

求 $S (199, 199)$ ，并将你的答案对 $1 000 000 007$ 取余。