Given an n × 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:

boardfontsize=18pt
showmover=false,
label=false,
maxfield=d3
showmover=false,
label=false,
maxfield=d3,
setpieces=na3
showmover=false,
label=false,
maxfield=d3,
setpieces=nc1,nc2,nb1
showmover=false,
label=false,
maxfield=d3,
setpieces=na1,na3,nc3,nd3

Input

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

Output

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

Public test cases

**Input**

1 1 1 10 2 1 3 4 4 2 4 10 4 1000000000000000

**Output**

2 1024 4 278 81 18702843 51397909

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++