Let's play with sequence of non negative integer. Given two sequence of n non negative integers (a₁, a₂ ... a_n) and (b₁, b₂ ... b_n). Both sequence has maximum element less than k, max(a_1, a₂ ... a_n) < k and max(b₁, b₂ ... b_n) < k. The game rule is you can edit both sequence with this operaton: swap a_i and b_i with 1 ≤ i ≤ n, and the goal is to make sequence a and b become increasing sequence: a_i ≤ a_j if and only if i ≤ j and b_i ≤ b_j if and only if i ≤ j. But not all initial sequence a and b can be solved.

For example (2, 0) and (0, 1) is a pair of sequence that can't be solved:

• If you don't swap any element, you have (2, 0) and (0, 1), but sequence (2, 0) is not increasing.
• If you swap first element only, then the pair become like this (0, 0) and (2, 1), sequence (2, 1) is not increasing.
• If you swap second element only, then the pair become like this (2, 1) and (0, 0), again (2, 1) is not increasing.
• If you swap both element, thrn the pair become like this (0, 1) and (2, 0), again (2, 0) is not increasing

So it's impossible to solve if initial sequence is (2, 0) and (0, 1), because all possible move can't make both sequence become increasing.

Now given n and k, your task is to compute number of different pair of initial sequence (a, b) that can be solved with game described above.

Input

First line there is an integer T denoting number of test case, then T test cases follow.

For each case, there are two integers n and k writen in one line, separated by a space.

Output

For each case, output number of different pair of initial sequence (a, b), since the answer can be large, output the answer modulo 10⁹+7.

Constraints

0 < T ≤ 10⁵

0 < min(n, k) ≤ 2

0 < max(n, k) < 10⁹

Example

Input:
6
2 1
1 2
1 3
2 2
3 2
2 3

Output:
1
4
9
11
26
46

Explanation

Here is list of all possible pair of initial sequence (a, b) on each case:

Case 1: {[(0, 0), (0, 0)]}

Case 2: {[(0), (0)], [(0), (1)], [(1), (0)], [(1), (1)]}

Case 3: {[(0), (0)], [(0), (1)], [(0), (2)], [(1), (0)], [(1), (1)], [(1), (2)], [(2), (0)], [(2), (1)], [(2), (2)]}

Case 4: {[(0, 0), (0, 0)], [(0, 0), (0, 1)], [(0, 0), (1, 1)], [(0, 1), (0, 0)], [(0, 1), (0, 1)], [(0, 1), (1, 0)], [(0, 1), (1, 1)], [(1, 0), (0, 1)], [(1, 1), (0, 0)], [(1, 1), (0, 1)], [(1, 1), (1, 1)]}

Case 5: {[(0, 0, 0), (0, 0, 0)], [(0, 0, 0), (0, 0, 1)], [(0, 0, 0), (0, 1, 1)], [(0, 0, 0), (1, 1, 1)], [(0, 0, 1), (0, 0, 0)], [(0, 0, 1), (0, 0, 1)], [(0, 0, 1), (0, 1, 0)], [(0, 0, 1), (0, 1, 1)], [(0, 0, 1), (1, 1, 0)], [(0, 0, 1), (1, 1, 1)], [(0, 1, 0), (0, 0, 1)], [(0, 1, 0), (1, 0, 1)], [(0, 1, 1), (0, 0, 0)], [(0, 1, 1), (0, 0, 1)], [(0, 1, 1), (0, 1, 1)], [(0, 1, 1), (1, 0, 0)], [(0, 1, 1), (1, 0, 1)], [(0, 1, 1), (1, 1, 1)], [(1, 0, 0), (0, 1, 1)], [(1, 0, 1), (0, 1, 0)], [(1, 0, 1), (0, 1, 1)], [(1, 1, 0), (0, 0, 1)], [(1, 1, 1), (0, 0, 0)], [(1, 1, 1), (0, 0, 1)], [(1, 1, 1), (0, 1, 1)], [(1, 1, 1), (1, 1, 1)]}

Case 6: {[(0, 0), (0, 0)], [(0, 0), (0, 1)], [(0, 0), (0, 2)], [(0, 0), (1, 1)], [(0, 0), (1, 2)], [(0, 0), (2, 2)], [(0, 1), (0, 0)], [(0, 1), (0, 1)], [(0, 1), (0, 2)], [(0, 1), (1, 0)], [(0, 1), (1, 1)], [(0, 1), (1, 2)], [(0, 1), (2, 2)], [(0, 2), (0, 0)], [(0, 2), (0, 1)], [(0, 2), (0, 2)], [(0, 2), (1, 0)], [(0, 2), (1, 1)], [(0, 2), (1, 2)], [(0, 2), (2, 0)], [(0, 2), (2, 1)], [(0, 2), (2, 2)], [(1, 0), (0, 1)], [(1, 0), (0, 2)], [(1, 1), (0, 0)], [(1, 1), (0, 1)], [(1, 1), (0, 2)], [(1, 1), (1, 1)], [(1, 1), (1, 2)], [(1, 1), (2, 2)], [(1, 2), (0, 0)], [(1, 2), (0, 1)], [(1, 2), (0, 2)], [(1, 2), (1, 1)], [(1, 2), (1, 2)], [(1, 2), (2, 1)], [(1, 2), (2, 2)], [(2, 0), (0, 2)], [(2, 1), (0, 2)], [(2, 1), (1, 2)], [(2, 2), (0, 0)], [(2, 2), (0, 1)], [(2, 2), (0, 2)], [(2, 2), (1, 1)], [(2, 2), (1, 2)], [(2, 2), (2, 2)]}

Other Info

Test case (n and k) is generated randomly using this rule:

• Probability that n > k or n ≤ k is ~50% each.
• Maximum n and k is random log-uniform.
• Minimum n and k is random uniform.

Click here if you want to know my program speed and other detail.

Time limit >100× my program top speed.

See also: Another problem added by Tjandra Satria Gunawan