Problem 416

A frog’s trip

A row of n squares contains a frog in the leftmost square. By successive jumps the frog goes to the rightmost square and then back to the leftmost square. On the outward trip he jumps one, two or three squares to the right, and on the homeward trip he jumps to the left in a similar manner. He cannot jump outside the squares. He repeats the round-trip travel m times.

Let $F (m, n)$ be the number of the ways the frog can travel so that at most one square remains unvisited.
For example, $F (1, 3) = 4$ , $F (1, 4) = 15$ , $F (1, 5) = 46$ , $F (2, 3) = 16$ and $F (2, 100) mod 10^{9} = 429619151$ .

Find the last $9$ digits of $F (10, 10^{12})$ .

青蛙的旅途

在一行n个方块的最左边一个上有一只青蛙。青蛙通过连续不断的跳跃，先跳到最右边的方块，然后再跳回最左边的方块。它向右跳的时候每次可以跳一个、两个或三个方块，跳回来时也同理。它不能跳出这些方块。这样的往返它一共进行了m次。

记 $F (m, n)$ 为青蛙在旅途中至多有一个方块从未被跳到过的方式总数。
例如， $F (1, 3) = 4$ , $F (1, 4) = 15$ , $F (1, 5) = 46$ , $F (2, 3) = 16$ ，而 $F (2, 100) mod 10^{9} = 429619151$ 。

求 $F (10, 10^{12})$ 的最后 $9$ 位数字。