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

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

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