For his gift, Inaho got a ~5 \times N~ grid of square cells, initially all white. He wants to colour exactly ~M~ cells black such that no two black cells are adjacent. Two cells are adjacent if they share a common side (so two cells which share only a corner are not adjacent). Output the number of ways to do this modulo ~10^9+7~.
- In test cases worth 25% of points, ~1 \leq N \leq 6~.
- In test cases worth 25% of points, ~7 \leq N \leq 10\,000~.
- In test cases worth 50% of points, ~10^8 \leq N \leq 10^9~.
In all test cases, ~0 \leq M \leq 50~.
The first and only line of input will contain ~N~ and ~M~ separated by a space.
A single line containing the answer.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3
Sample Input 4
Sample Output 4