마카롱

피에르는 마카롱을 만든다. 동그란 마카롱은 1 × 1 크기의 정사각형 상자에 담고, 타원형 마카롱은 1 × 2 크기의 직사각형 상자에 담는다. 직사각형 상자는 돌려서 2 × 1 크기로 놓을 수도 있다.

뷔페를 준비하는 피에르는 N × M 크기의 직사각형 탁자를 이 두 종류의 상자로 빈틈없이 덮으려고 한다. 상자끼리 겹칠 수 없고, 탁자 밖으로 나갈 수도 없다. 상자의 변은 항상 탁자의 변과 나란하다. 손님이 마카롱을 쉽게 집도록 탁자의 폭 N은 작고, 손님을 많이 받도록 탁자의 길이 M은 크다.

탁자를 덮는 방법이 몇 가지인지 구하라.

첫째 줄에 정수 N이 주어진다.

둘째 줄에 정수 M이 주어진다.

제한

1 ≤ N ≤ 8, 1 ≤ M ≤ $10^{18}$

탁자를 덮는 방법의 수를 $10^9$으로 나눈 나머지를 한 줄에 출력한다.