Xiangqi - MarisaOJ: Marisa Online Judge

Xiangqi

Time limit: 1000 ms
Memory limit: 256 MB
Given a Xiangqi (Chinese Chess) board with dimensions $n \times m$, count the number of ways to place knights on the board so that no two knights attack each other. The number of knights placed on the board can be arbitrary. In Xiangqi, the pieces are placed on the intersections of the lines. Also, the movement of the knights in Xiangqi is as follows: - Knights move in an L-shape. - However, if a knight is blocked by another piece in front of it, it cannot move. ### Input - A single line containing two positive integers $n, m$. ### Output - Print the number of ways to place the knights satisfying the condition modulo $10^9+7$. ### Constraints - $1 \le n \le 6$. - $1 \le m \le 100$. ### Example Input: ``` 3 3 ``` Output: ``` 145 ```