Knights P19852

Given an $n \times m$ chess board, you can place on it as many black knights as you wish, as long as no two knights threaten each other. How many possibilities do you have?

For instance, these are just four of the 278 possibilities for $n = 3$ and $m = 4$:

Input

Input consists of several cases, each with $n$ and $m$. Assume $1 \le n \le 4$ and $1 \le m \le 10^{15}$.

Output

For every case, print the number of possibilities modulo $10^8 + 7$.