文理学院程序设计在线练习


Special Knight

Time Limit: 3 Second(s)    Memory Limit: 32 MB

Total Submission(s): 23   Accepted Submission(s): 9
Problem Description

Special knight is a special chess which can move to a square that is two squares away horizontally and one square vertically, and he can only move once. In other words, the special knight can only move to previous row and next row, which is different from common knights. Given a chessboard whose size is n*m. You can put any number of special knights on it. Asking how many kinds of method can assure that, the knights will not kill other special knights.

Input

Multiple cases (<=10).
For each test case, there’s one line consisting of two integers n, m(1 <= n <= 1000000000, 1 <= m <= 6)

Output

For each test case, output one line, representing the answer mod 1000000007.

Sample Input
2 3
Sample Output
36
Source

2017绍兴市联赛