﻿# -*- coding: utf-8 -*-
# ProjectEuler/src/python/problem416.py
#
# A frog's trip
# =============
# Published on Saturday, 23rd February 2013, 01:00 pm
#
# 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 109 = 429619151. Find the last 9 digits of
# F(10, 1012).

import projecteuler as pe

def main():
    pa
if __name__ == "__main__":
    main()

ss

