---

Problem 947

---

Fibonacci Residues

The $(a,b,m)$-sequence, where $0 \leq a,b \lt m$, is defined as

$$\begin{aligned}
g(0)&=a\\
g(1)&=b\\
g(n)&= \big(g(n-1) + g(n-2)\big) \bmod m
\end{aligned}$$

All $(a,b,m)$-sequences are periodic with period denoted by $p(a,b,m)$.

The first few terms of the $(0,1,8)$-sequence are $(0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,\ldots )$ and so $p(0,1,8)=12$.

Let $\displaystyle s(m)=\sum_{a=0}^{m-1}\sum_{b=0}^{m-1} p(a,b,m)^2$. For example, $s(3)=513$ and $s(10)=225820$.

Define $\displaystyle S(M)=\sum_{m=1}^{M}s(m)$. You are given, $S(3)=542$ and $S(10)=310897$.

Find $S(10^6)$. Give your answer modulo $999\ 99\ 893$.

---

斐波那契余数

对于$0 \leq a,b \lt m$，定义$(a,b,m)$-数列如下：

$$\begin{aligned}
g(0)&=a\\
g(1)&=b\\
g(n)&= \big(g(n-1) + g(n-2)\big) \bmod m
\end{aligned}$$

所有$(a,b,m)$-数列都是周期性的，其周期记为$p(a,b,m)$。

例如，$(0,1,8)$-数列的前几项为$(0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,\ldots )$，因此$p(0,1,8)=12$。

记$\displaystyle s(m)=\sum_{a=0}^{m-1}\sum_{b=0}^{m-1} p(a,b,m)^2$。例如，$s(3)=513$，$s(10)=225820$。

定义$\displaystyle S(M)=\sum_{m=1}^{M}s(m)$。已知$S(3)=542$，$S(10)=310897$。

求$S(10^6)$，并对$999\ 999\ 893$取余作为你的答案。

---