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

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

Входные данные

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

Выходные данные

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

Примеры