F. Large Tiling With Dominoes
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

A domino on a grid is a shape consisting of two unit squares with a common side. For an $$$m \times n$$$ rectangle, a domino tiling is a set of dominoes which are completely inside the rectangle such that each square of the rectangle is covered by exactly one of them. Two tilings $$$P$$$ and $$$Q$$$ are considered different if there are dominoes $$$p \in P$$$ and $$$q \in Q$$$ which share exactly one square.

How many ways are there to tile a rectangle of size $$$m \times n$$$ with dominoes? Since the number of ways can be very large, you need to output the answer modulo $$$10^9 + 7$$$.

Input

The first line of input contains two integers $$$m$$$ and $$$n$$$: the height and width of the rectangle, respectively ($$$1 \le m \le 6$$$, $$$1 \le n \le 10^{18}$$$).

Output

Output a single integer: the number of ways to tile the rectangle $$$m \times n$$$ with dominoes modulo $$$10^9 + 7$$$.

Examples
Input
3 4
Output
11
Input
3 1
Output
0