Funny Function

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

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.

Sample Input

2 2 2 3 3

Sample Output

2 33

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码