---

Problem 915

---

Giant GCDs

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$.

---

超大的最大公约数

对正整数递归定义函数$s(n)$如下：$s(1)=1$；对$n\ge 1$，$s(n+1)=(s(n)-1{)}^3+2$。

该序列的最初几项分别是：$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$取余作为你的答案。

---