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的余数