Now, they are outside a cave marked in the map which was found under the lake. They enter the cave. After entering the cave, they see m tunnels and each of these tunnels lead to a further n tunnels. They wonder in how many different ways can they cross the cave. Since none of them find it too easy, they are asking for your help to solve the problem. Can you help them? Print the answer modulo \(10^9\)+7.

Input:

First line contains an integer T denotes the number of test cases. Each of the following T lines contains two integers m and n.

Output:

For each testcase,print the number of different paths modulo \(10^9\)+7.

Constraints:

1 <= T <= 50

1 <= m <= \(10^5\)

1 <= n <= \(10^5\)

Subtasks:

Subtask #1 (30 points): 1 <= m,n <= 1000

Subtask #2 (70 points): original constraints

Input:

2
1 3
5 8

Output:

3
40