Funny Function

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.

Sample Input

2

2 2

3 3

Sample Output

2

33

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6050