Knights P19852
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 ≤ 1015.
Output
For every case, print the number of possibilities modulo 108 + 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++