ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Путешествие лучника

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Назовём лучником шахматную фигуру, способную ходить на одно поле вперёд, назад, влево или вправо. Лучник стоит на поле (1, 1) шахматной доски размера N на M (правое верхнее поле такой доски имеет номер (N, M)). Цель лучника — обойти всю доску и вернуться в исходное поле, причём в процессе путешествия он должен побывать на каждом поле доски в точности один раз (путешествие начинается с момента первого хода лучника). Хотелось бы узнать, сколькими способами лучник может обойти доску.

Исходные данные

Целые числа N и M, разделённые пробелом. 2 ≤ N ≤ 5; 2 ≤ M ≤ 109.

Результат

Выведите единственное число — количество способов обойти доску, вычисленное по модулю 109.

Пример

исходные данныерезультат
2 3
2
Автор задачи: Александр Ипатов (подготовка — Владимир Яковлев)
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1459. Путешествие лучника