ProjectEuler 490 Jumping frog - 拼圖

490. Jumping frog

http://projecteuler.net/problem=490

池塘中有n個石頭，編號從1到n，編號相鄰的石頭間隔為一單位距離

一隻青蛙坐在編號為1的石頭上，它想要拜訪每個石頭恰好一次，最後停在編號n的石頭上
然而，他只能從一顆石頭跳到另一顆石頭假若其間隔的距離最多為3單位遠。

換句話說，若青蛙在編號為i的石頭上，它僅能抵達編號為j的石頭上, 1<=j<=n
且j為集合{i-3, i-2, i-1, i+1, i+2, i+3}中的某一元素

令f(n)為青蛙能如此做的方法數，例如，f(6)=14，所有的方法數顯示如下:

1 → 2 → 3 → 4 → 5 → 6
1 → 2 → 3 → 5 → 4 → 6
1 → 2 → 4 → 3 → 5 → 6
1 → 2 → 4 → 5 → 3 → 6
1 → 2 → 5 → 3 → 4 → 6
1 → 2 → 5 → 4 → 3 → 6
1 → 3 → 2 → 4 → 5 → 6
1 → 3 → 2 → 5 → 4 → 6
1 → 3 → 4 → 2 → 5 → 6
1 → 3 → 5 → 2 → 4 → 6
1 → 4 → 2 → 3 → 5 → 6
1 → 4 → 2 → 5 → 3 → 6
1 → 4 → 3 → 2 → 5 → 6
1 → 4 → 5 → 2 → 3 → 6

其他的例子為f(10) = 254 和 f(40) = 1439682432976

令S(L)為 1<=n<=L的條件下，所有f(n)^3的總和

一些例子：
S(10) = 18230635
S(20) = 104207881192114219
S(1 000) 除 10^9 = 225031475
S(1 000 000) 除 10^9 = 363486179

請求出S(10^14) 除 10^9的餘數

--