Chess - MarisaOJ: Marisa Online Judge

Chess

Time limit: 1000 ms
Memory limit: 256 MB
Count the number of ways to place knights on a chessboard of size $n \times m$ such that they do not attack each other. ### Input - A single line contains two integers $n,m$. ### Output - Print the number of way modulo $10^9+7$. ### Constraints - $ 1 \le n \le 10^9, 1 \le m \le 4$. ### Example Input: ``` 2 2 ``` Output: ``` 16 ```
Topic
Dynamic Programming
Matrix
Bitmasks
Rating 1800
Solution (0) Solution