从两个字符串 $S_0=0$ 和 $S_1=01$ 开始，我们将 $S_n$ 定义为 $S_{n-1}{S}_{n-2}$ for $n\ge 2$ 的串联。
例如，$S_2=010$、$S_3=01001$ 和 $S_4=01001010$。
如果一个字符串是某个 $S_n$ 的子字符串连续子序列，则该字符串称为斐波那契子字。

有趣的是，对于每个正整数 $k$，只有 $k+1$ 个长度为 $k$ 的不同斐波那契子字。我们将它们解释为十进制数（忽略前导零）并令 $\mathrm{\Psi }(k)$ 为它们的平方和。

例如，长度为 $3$ 的四个不同的斐波那契子字是 $001,010,100,101$。因此 $\mathrm{\Psi }(3)=1^2+{10}^2+{100}^2+{101}^2=20302$。
您还将获得 $\mathrm{\Psi }(10)\equiv 10699667(\mathrm{mod}101001001)$。

求 $\mathrm{\Psi }({10}^{18})mod101001001$。