ProjectEuler 440 GCD and Tiling - 拼圖

440. GCD and Tiling

http://projecteuler.net/problem=440

有一塊尺寸為1 ×n的板子。

我們想要用1 ×2的方塊和1 ×1並且上面有個位數號碼的方塊來舖滿它：

http://projecteuler.net/project/images/p440_tiles.png

例如，下列為一小部分將n = 8的板子用這些方塊舖滿的方法：

http://projecteuler.net/project/images/p440_some8.png

令T(n)為將長度為n的板子用這些方塊舖滿的方法數。

例如，T(1) = 10以及T(2) = 101。

令S(L)為Σgcd(T(c^a), T(c^b))對所有1≦a,b,c≦L得到的三重和。

例如：

S(2) = 10444
S(3) = 1292115238446807016106539989
S(4) mod 987898789 = 670616280

請求出S(2000) mod 987898789。

--