Мандрівка лучника

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

Вхідні дані

Натуральні числа n та m (2 ≤ n ≤ 5, 2 ≤ m < 10^9).

Вихідні дані

Виведіть кількість способів обійти дошку, обчислену за модулем 10^9.

Приклади