Задачі
Мандрівка лучника
Мандрівка лучника
Назвемо лучником шахову фігуру, здатну ходити на одне поле вперед, назад, ліворуч та праворуч. Лучник стоїть на полі (1, 1) шахової дошки розміром n × m (праве верхнє поле такої дошки має номер (n, m)). Мета лучника - обійти усю дошку і повернутись на початкове поле, причому у процесі подорожі він повинен побувати на кожному полі дошки точно один раз (пдорож розпочинається з моменту першого ходу лучника). Хотілось би взнати, скількома способами лучник може обійти дошку.
Вхідні дані
Натуральні числа n та m (2 ≤ n ≤ 5, 2 ≤ m < 109
).
Вихідні дані
Виведіть кількість способів обійти дошку, обчислену за модулем 109
.
Вхідні дані #1
2 3
Вихідні дані #1
2