我们想要完全平铺一块长度为 $n$、高度为 $1$ 的棋盘，其中可以是 $1\times 2$ 块，也可以是 $1\times 1$ 块，顶部有一个小数位：

例如，以下是平铺长度为 $n=8$ 的木板的一些方法：

令 $T(n)$ 为平铺长度为 $n$ 的木板的方法数量，如上所述。

例如，$T(1)=10$ 和 $T(2)=101$。

设 $S(L)$ 为 $1\le a,b,c\le L$ 的三重和 $\sum _{a,b,c}gcd(T(c^a),T(c^b))$。
例如：
$S(2)=10444$
$S(3)=1292115238446807016106539989$
$S(4)mod987898789=670616280$。

求 $S(2000)mod987898789$。