Starting with two strings $S_0=0$ and $S_1=01$, we define $S_n$ as the concatenation $S_{n-1}{S}_{n-2}$ for $n\ge 2$.
For example, $S_2=010$, $S_3=01001$ and $S_4=01001010$.
A string is called a Fibonacci subword if it is a substringcontiguous subsequence of some $S_n$.

Interestingly, for each positive integer $k$, there are only $k+1$ different Fibonacci subwords of length $k$. We interpret them as decimal numbers (ignoring leading zeros) and let $\mathrm{\Psi }(k)$ be the sum of their squares.

For example, the four different Fibonacci subwords of length $3$ are $001,010,100,101$. Therefore $\mathrm{\Psi }(3)=1^2+{10}^2+{100}^2+{101}^2=20302$.
You are also given $\mathrm{\Psi }(10)\equiv 10699667(\mathrm{mod}101001001)$.

Find $\mathrm{\Psi }({10}^{18})mod101001001$.