ProjectEuler 416 A frog's trip - 拼圖

416. A frog's trip

http://projecteuler.net/problem=416

一隻青蛙停在一排長度為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)的最後九位數。

--