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.

Multiple cases (<=10).

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

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