池塘里有 $n$ 石头，编号为 $1$ 到 $n$。连续的石子间隔一单位。

一只青蛙坐在石头 $1$ 上。他希望每块石头都访问一次，并在 $n$ 石头上停下来。然而，他只能从一块石头跳到另一块石头，前提是它们之间的距离最多为 $3$ 单位。换句话说，如果 $1\le j\le n$ 和 $j$ 在集合 $\{i-3,i-2,i-1,i+1,i+2,i+3\}$ 中，那么从石头 $i$ 开始，他可以到达石头 $j$。

令 $f(n)$ 为他可以做到这一点的方法数量。例如$f(6)=14$，如下图：
$1\to 2\to 3\to 4\to 5\to 6$
$1\to 2\to 3\to 5\to 4\to 6$
$1\to 2\to 4\to 3\to 5\to 6$
$1\to 2\to 4\to 5\to 3\to 6$
$1\to 2\to 5\to 3\to 4\to 6$
$1\to 2\to 5\to 4\to 3\to 6$
$1\to 3\to 2\to 4\to 5\to 6$
$1\to 3\to 2\to 5\to 4\to 6$
$1\to 3\to 4\to 2\to 5\to 6$
$1\to 3\to 5\to 2\to 4\to 6$
$1\to 4\to 2\to 3\to 5\to 6$
$1\to 4\to 2\to 5\to 3\to 6$
$1\to 4\to 3\to 2\to 5\to 6$
$1\to 4\to 5\to 2\to 3\to 6$

其他示例有 $f(10)=254$ 和 $f(40)=1439682432976$。

让 $S(L)=\sum f(n{)}^3$ 为 $1\le n\le L$。
示例：
$S(10)=18230635$
$S(20)=104207881192114219$
$S(1000)mod{10}^9=225031475$
$S(1000000)mod{10}^9=363486179$

查找 $S({10}^{14})mod{10}^9$。