The function $s(n)$ is defined recursively for positive integers by $s(1)=1$ and $s(n+1)=(s(n)-1{)}^3+2$ for $n\ge 1$.
The sequence begins: $s(1)=1,s(2)=2,s(3)=3,s(4)=10,\dots$.

For positive integers $N$, define $$T(N)=\sum _{a=1}^N\sum _{b=1}^{N}gcd(s(s(a)),s(s(b))).$$ You are given $T(3)=12$, $T(4)\equiv 24881925$ and $T(100)\equiv 14416749$ both modulo $123456789$.

Find $T({10}^8)$. Give your answer modulo $123456789$.