cho.sh

Macarons

Count the ways to tile an N by M rectangle with 1x1 and 1x2 dominoes, with N at most 8 and M up to 10^18, modulo 10^9.

Medium7Dynamic programmingBit manipulationMatrixCombinatoricsNo attempts yetTime limit5sMemory limit512 MB

Problem

Rows of macarons in many colors

Pierre makes macarons. Round macarons go into square boxes of size 1 × 1, and oval macarons go into rectangular boxes of size 1 × 2. A rectangular box can be turned to sit as a 2 × 1 box instead.

For a buffet, Pierre wants to cover a rectangular table of size N × M with these two kinds of boxes so that no empty space is left. Boxes cannot overlap and cannot stick out of the table. The sides of a box always stay parallel to the sides of the table. The width N of the table is small, so that a guest can grab the macarons easily, and the length M is large, so that the table serves many guests.

Count the number of ways to cover the table.

Input

The first line contains the integer N.

The second line contains the integer M.

Limits

1 ≤ N ≤ 8, 1 ≤ M ≤ 101810^{18}

Output

Print the number of ways to cover the table modulo 10910^9 on a single line.