Macarons
Pierre is famous for his macarons. He makes round macarons, stored in square boxes of size 1 * 1, and oval-shaped macarons, stored in rectangular boxes of size 1 * 2 (or, rotated, in rectangular boxes of size 2 * 1). For the purpose of a buffet, Pierre wishes to tile a rectangular table of size n * 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
Two integers n (1 ≤ n ≤ 8) and m (1 ≤ m ≤ 10^18).
Output
Print the total number of tilings, given modulo 10^9.