Мандрівка лучника#3442
Назвемо лучником шахову фігуру, здатну ходити на одне поле вперед, назад, ліворуч та праворуч. Лучник стоїть на полі шахової дошки розміром n \times m (праве верхнє поле такої дошки має номер ). Мета лучника — обійти усю дошку і повернутись на початкове поле, причому у процесі подорожі він повинен побувати на кожному полі дошки точно один раз (подорож розпочинається з моменту першого ходу лучника). Хотілось би дізнатися, скількома способами лучник може обійти дошку.
Натуральні числа та (2 \leq n \leq 5, 2 \leq m < 10^9).
Виведіть кількість способів обійти дошку, обчислену за модулем 10^9.
Приклад 1