One morning, you realize that binary matrices are irresistible. You just can't stop thinking about them. You realize that you had inherited your love of binary matrices from your math teacher, Mr. Sidhu!

Thinking back a little, this is because Mr. Sidhu had left you a homework problem to be completed by last period today. And you didn't even start on it! Luckily, you have a few minutes before class starts. You take a look at the problem again:

Determine the number of binary matrices of size ~R \times C~ that have at least one 1 entry in each row and column, modulo ~10^9+7~.

Since there are a lot of problems of this form, specifically ~T~ of these problems, you would like to write a program that solves these quickly, or risk getting a mark below 100 in math!

Input Specification

The first line of input will have the number of test cases, ~T~. The next ~T~ lines will each contain a test case.

Each test case is one line with ~R~ and ~C~ separated by a single space.

Output Specification

For each test case, output the answer. Remember to take it modulo ~10^9+7~.

Constraints

There will be 5 subtasks each worth 20% of the points for this problem.

• ~T \le 16; R \le 4; C \le 4~
• ~T \le 36; R \le 6; C \le 6~
• ~T \le 500; R \le 500; C \le 500~
• ~T \le 10; R \le 10^9; C \le 6~
• ~T \le 10; R \le 10^9; C \le 3\,000~

In all subtasks, ~T, R, C \ge 1~.

Tips

Optimize your program to run as fast as possible, even if you think it has the correct complexity.

Sample Input

4
1 1
2 2
2 3
3 2

Sample Output

1
7
25
25

Explanation

The seven matrices for the ~R = C = 2~ case are:

11
11

11
10

11
01

10
11

01
11

01
10

10
01

Original Problem Author: No_stop; Problem Resource: HDU 5155