416 : カエルの旅行

一番左のマスにカエルがいるn個のマスの列がある。 連続してジャンプすることにより、カエルは一番右のマスに移動し、再び一番左のマスに戻ってくる。 下り（最初のマスから離れる方へ向かう）のときはカエルは右へ1マス、2マス、あるいは3マスジャンプする。そして上り（最初のマスへ近づく方へ向かう）の時は同様にして左にジャンプする。 カエルはマスの外には移動できない。カエルはこの往復をm回繰り返す。

カエルが旅行をする方法のうち、訪れることなく残されるマスがたかだかひとつになるようなやり方の数を $F(m,n)$としよう。

例えば、$F(1, 3) = 4$, $F(1, 4) = 15$, $F(1, 5) = 46$, $F(2, 3) = 16$, $F(2, 100) \bmod 10^9 = 429619151$ となる。

$F(10, 10^{12})$の末尾9桁を求めよ。