J :: International Cord Pulling Contest

Time Limit: 2 Seconds    Memory Limit: 65536 KB

The International Cord Pulling Contest (ICPC) is very special series of contests hosted by ShareCord every year. This year ShareCord’s founders are pretty excited about the contest, because there is going to be an elders team formed from the old members of the federation. As they are pretty old and cranky, if they lose the game, they’ll be pissed off and will leave the federation forever which is very bad for the federation’s reputation. And it is also bad if they win the game since it discourages the younger contestants. The only way federation could get away is to arrange a perfect team with the exact strength as elders’ team so they’ll tie.

Arranging a perfect team is not that easy as there is another condition: In order to make it not suspicious, ShareCord need to make sure each member of the perfect team’s strength is not less than a special amount called suspicious level.

There is no limit on the number of people in the team, but it should have at least one member. The strength of the team is the sum of strength of each team member and the strength of each member is an integer greater than zero. As each member will have a position number indicating which point of the cord he should hold at, the order is important too.

Assume the total strength of the elder’s team is 3. So we have these three options to form the team:

  • {3}
  • {2, 1}
  • {1, 2}
  • {1, 1, 1}

Here for example, for suspicious level equal to 2, only those formations that all members’ strengths are greater than or equal 2 would be accepted. So there is only one option:

  • {3}

If the suspicions level is 1, all of those 4 combination would be accepted.

Now it is your task to write a program to compute the number of possible ways to form the perfect team given the strength of elder’s team and the suspicious level.

You can assume the ShareCord community is huge and you can find infinite number of people with desired strength.

Input

The input contains several test cases.

In the first line of input comes T (0 < T < 32), the number of test cases.

Each test case is one line with two integer N (0 < N ≤ 109) and K (0 < K < 31), indicating the strength of the elder’s team and the suspicious level respectively.

Output

For each test print the total number of ways to form the perfect team modulo 109 + 7.

Sample Input

3
4 2
3 1
3 2

Sample Output

2
4
1
Submit

Source: 13th Iran Nationwide Internet Contest - UT