В самом левом квадрате ряда из 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⁹ = 429619151.

Найдите последние 9 цифр F(10, 10¹²).