<p> Начиная с двух строк $S_0 = 0$ и $S_1 = 01$, определим $...

Prompt

<p> Начиная с двух строк $S_0 = 0$ и $S_1 = 01$, определим $S_n$ как конкатенацию $S_{n − 1}S_{n − 2}$ для $n \ge 2$.<br> Например, $S_2 = 010$, $S_3 = 01001$ и $S_4 = 01001010$.<br> Строка называется <dfn> подсловом Фибоначчи</dfn>, если это <strong class="всплывающая подсказка">подстрока<span class="tooltiptext">непрерывная подпоследовательность</span></strong> некоторого $S_n$.</p> <p> Интересно, что для каждого натурального числа $k$ существует всего $k + 1$ различных подстрок Фибоначчи длиной $k$. Мы интерпретируем их как десятичные числа (без ведущих нулей) и пусть $\Psi(k)$ — сумма их квадратов. </p> <p> Например, четыре различных подстроки Фибоначчи длиной $3$ — это $001, 010, 100, 101$. Следовательно, $ \ Psi(3) = 1^2 + 10^2 + 100^2 + 101^2 = 20302$.<br> Вам также дается $\ Psi(10) \equiv 10699667 \pmod{101001001} $.</p> <p> Найдите $\Psi(10^{18}) \bmod 101001001$.</p>