Мы хотим выложить стол длиной n и шириной 1 без зазоров или плитками 1 × 2, или плитками 1 × 1, подписанными одной десятичной цифрой:

Например, вот несколько способов выложить плиткой стол длиной n = 8:

Пусть T(n) будет количеством способов выложить плиткой стол длиной n указанным выше способом.

Например, T(1) = 10 и T(2) = 101.

Пусть S(L) будет тройной суммой ∑_a,b,c НОД(T(c^a), T(c^b)) для 1 ≤ a, b, c ≤ L.
Например:
S(2) = 10444
S(3) = 1292115238446807016106539989
S(4) mod 987 898 789 = 670616280.

Найдите S(2000) mod 987 898 789.