Macarons#9672
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, when rotated, in rectangular boxes of size 2 \times 1). For a buffet, Pierre wishes to tile a rectangular table of size n \times m with the two types of macarons so that the table is completely filled, with no empty spaces. The width of the table is small, allowing guests to easily reach the macarons, and the length is large to accommodate a great number of guests. For aesthetic reasons, the orientation of the macarons must always be aligned with the sides of the table.
Pierre wants to know in how many ways it is possible to tile the table. Can you help him?
Two integers (1 \le n \le 8) and (1 \le m \le 10^{18}).
Print the total number of ways to tile the table, modulo 10^9.
Example 1
Example 2