Problem Description

Function $F_{x,y}$satisfies:

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.

Input

There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<2^63.

Output

For each given N and M,print the answer in a single line.

2
2 2
3 3

2
33