SWAP_ESY - Swap (Easy - Level 2)

Let's play with sequence of non negative integer. Given two sequence of n non negative integers (a1, a2 ... an) and (b1, b2 ... bn). Both sequence has maximum element less than k, max(a1, a2 ... an) < k and max(b1, b2 ... bn) < k. The game rule is you can edit both sequence with this operaton: swap ai and bi with 1 ≤ in, and the goal is to make sequence a and b become increasing sequence: ai ≤ aj if and only if ij and bi ≤ bj if and only if ij. 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 109+7.

Constraints

0 < T ≤ 105

0 < min(n, k) ≤ 2

0 < max(n, k) < 109

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 nk 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


Added by:Tjandra Satria Gunawan
Date:2013-06-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Modified Swap (Original) problem

hide comments
2013-12-22 05:44:30 Ankit Kumar
Nice one.. although you can put a more strict time limit on it

Last edit: 2013-12-22 08:00:20
2013-06-23 13:52:25 Michael Kharitonov
ai≤aj if and only if i<j
by your defenition there are no increasing sequences (consider i=j)
by "increasing" you mean non-decreasing?
Ans: Problem statement has been updated, thanks for your catch :-)
And of course I mean non decreasing. It's only "increasing", not "srictly increasing" by the definition from Wikipedia.

Last edit: 2013-06-23 13:58:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.