函数 $s(n)$ 对于正整数递归地定义为 $s(1)=1$ 和 $s(n+1)=(s(n)-1{)}^3+2$ 对于 $n\ge 1$。
序列开始于：$s(1)=1,s(2)=2,s(3)=3,s(4)=10,\dots$。

对于正整数 $N$，定义 $$T(N)=\sum _{a=1}^N\sum _{b=1}^{N}gcd(s(s(a)),s(s(b))).$$ 给出 $T(3)=12$、$T(4)\equiv 24881925$ 和 $T(100)\equiv 14416749$ 均以 $123456789$ 为模。

求$T({10}^8)$。以 $123456789$ 为模给出你的答案。