$(a,b,m)$ 序列，其中 $0\le a,b<m$ 定义为

$\begin{array}{rl}g(0)& =a\\ g(1)& =b\\ g(n)& =(g(n-1)+g(n-2))modm\end{array}$

所有 $(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,\dots )$，因此$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)$。以 $999999893$ 为模给出你的答案。