Xiao Ming likes playing the international chess ,especially like the elephant(it can move by slant while no barrier),
but he think the big elephant of the chess is cruel,and a kind of small elephant is not as cruel as the big elephant.
Its attack range is checks on the ramp of the small elephant's check's right angle.Now Ming is going to put many small elephants on his chessboard.
It's interesting that when two small elephants have a common side they'll become one solidarity elephant,
and more than 2 small elephants also can do this if satisfy the condition,and the attack range of solidarity elephants is same as the small elephant.
Now there is a requirement that it's empty on anyone of elephants' attack range(no piece).Xiao Ming has a special chessboard with $m*n$ checks.
Please figure out the number of all the plans that satisfy the condition.As the number is too big,we need to have a modulo $1000000007$.
The following is pictures show the attack range of elephants with different shape,"X"means attack range.
Input
There are at most $5$ testcases .
For each testcase contains two integers $n,m$ ,meaning as in the title.
$1 \leq n \leq 1000000000,1 \leq m\leq 7$
Output
For each testcase print a single integer - the number of all the plans that satisfy the condition.
