, чтобы сохранить свой прогресс
Проблема 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 109 = 429619151.
Найдите последние 9 цифр F (10, 1012).
/**
* Your test output will go here.
*/