Макарони#9672
П'єр відомий своїми макаронами. Він виготовляє круглі макарони, які зберігаються в квадратних коробках розміром 1 \times 1, та овальні макарони, які зберігаються в прямокутних коробках розміром 1 \times 2 (або, якщо повернути, в прямокутних коробках розміром 2 \times 1). Для фуршету П'єр хоче заповнити прямокутний стіл розміром n \times m цими двома видами макаронів так, щоб стіл був повністю заповнений, без порожніх місць. Ширина столу мала, щоб гості могли легко взяти макарони, а довжина велика, щоб вмістити багато гостей. Для краси орієнтація макаронів має завжди відповідати сторонам столу.
П'єр хоче знати, скільки існує способів заповнити стіл. Ви можете йому допомогти?
Два цілих числа (1 \le n \le 8) і (1 \le m \le 10^{18}).
Виведіть кількість способів повністю заповнити стіл за модулем 10^9.
Приклад 1
Приклад 2