Рассмотрим сетку $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 \pmod{1\,000\,000\,007}$.

Пусть $f_1=f_2 = 1$ и $f_n=f_{n-1}+f_{n-2}, n \ge 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 \pmod{1\,000\,000\,007}$.

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