data/problems/416.yml
---
:id: 416
:name: A frog's trip
:url: https://projecteuler.net/problem=416
:content: "A row of <var>n</var> 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 <var>m</var> times.\n\nLet F(<var>m</var>,
<var>n</var>) be the number of the ways the frog can travel so that at most one
square remains unvisited. \nFor example, F(1, 3) = 4, F(1, 4) = 15, F(1, 5) = 46,
F(2, 3) = 16 and F(2, 100) mod 10<sup>9</sup> = 429619151.\n\nFind the last 9 digits
of F(10, 10<sup>12</sup>).\n\n"