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