Pierre is famous for his macarons. He makes round macarons, stored in square boxes of size ~1 \times 1~, and oval-shaped macarons, stored in rectangular boxes of size ~1 \times 2~ (or, rotated, in rectangular boxes of size ~2 \times 1~). For the purpose of a buffet, Pierre wishes to tile a rectangular table of size ~N \times M~ with the two kinds of macarons, meaning that the table must be completely full, with no empty space left. The width ~N~ of the table is small, for the guest to be able to grab the macarons easily, and the length ~M~ of the table is large, to accommodate a huge number of guests. To keep the table pretty, the orientation of macarons should always be aligned with the sides of the table.

Pierre wishes to know how many ways there are to tile the table. Can you help him?

Input Specification

The input consists of the following integers:

• the value of ~N~, an integer, on the first line;
• the value of ~M~, an integer, on the second line.

Constraints

The input satisfies ~1 \le N \le 8~ and ~1 \le M \le 10^{18}~.

Output Specification

The output should consist of the total number of tilings, given modulo ~10^9~, on a single line.

Sample Input 1

2
2

Sample Output 1

7

Sample Input 2

2
4

Sample Output 2

71