SWAP_MED - Swap (Medium - Level 200)

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 operation: 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, then 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) ≤ 200

0 < max(n, k) < 1018

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.

Explanation about my Algorithm complexity:

My 2.8KB of python 3 code that got AC in 18.7s, the complexity is O(min(n, k)3) "This is direct translation [line by line] of my C code, there are many room for optimisations like fast I/O, data structure, etc"

My 3.7KB of C code that got AC in 6.36s, the complexity is O(min(n, k)4)

My 3.8KB of C code that got AC in 0.53s, the complexity is O(min(n, k)3) "Note that although the size of code is similar, but my O(min(n, k)4) and O(min(n, k)3) code is very different"

To challenge fast language user with O(min(n, k)3) complexity, I made this Hard version. For slow language user this medium version will be look like hard version ;-) good luck.

About complexity, I've proved using math that no algo with complexity better than O(min(n, k)2), this is the lower bound. My best algo for now is O(min(n, k)3), this is the upper bound. So the optimal algo lies between that lower and upper bound. I still don't have proof that my algo is optimal, so there is possibility that there is an algorithm that better than O(min(n, k)3).

Time limit ~37× my program top speed.


See also: Another problem added by Tjandra Satria Gunawan


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

hide comments
2013-06-23 23:04:43 Robert Gerbicz
Tjandra, any (small) input where my latest code breaks? Checked n,k in {50,51,52} and some small inputs.
Ans: Your code is very near to AC :-) try this tricky(?) case: n=200 and k=201, and your code will output strange answer which obviously wrong ;-)
re: OK, solved.

Last edit: 2013-06-24 01:25:46
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.