Назовём лучником шахматную фигуру, способную ходить на одно поле вперёд, назад, влево или вправо. Лучник стоит на поле (1, 1) шахматной доски размера n × m (правое верхнее поле такой доски имеет номер (n, m)). Цель лучника – обойти всю доску и вернуться в исходное поле, причём в процессе путешествия он должен побывать на каждом поле доски в точности один раз (путешествие начинается с момента первого хода лучника). Хотелось бы узнать, сколькими способами лучник может обойти доску.
Натуральные числа n и m (2 ≤ n ≤ 5, 2 ≤ m < 10^9
).
Выведите количество способов обойти доску, вычисленное по модулю 10^9
.