Funny Function
TimeLimit:1000MS MemoryLimit:32768KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
Function $F_{x,y}$satisfies:
For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.
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.
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.
SampleInput
2 2 2 3 3
SampleOutput
2 33