Kapish is a huge fan of football. He loves anything and everything related to the game and never misses a single match when his favourite team, Manchester United, is playing. Being the coder that he is, one day he decides to create his own, slightly modified version of football, through code.

The game is played between 2 teams having M players each and continues for N minutes. In each minute of the game, exactly one of the following 5 events will take place:

1. Team 1 scores a goal
2. Team 2 scores a goal
3. A player from team 1 gets a red card
4. A player from team 2 gets a red card
5. None of the above

A player who gets a red card can take no further part in the game. If at any point of time, a team is left with less than 5 players on the field, it will automatically get disqualified, and the other team will be declared as the winner.

Kapish is very pleased with his new game. However, Pushap, who hates boring draws in football, is not impressed. “Do you even know how many ways are there for this game to end in a draw?” he asks.

Given N and M, can you help Kapish find out the number of ways for the game to end in a draw? (draw means both teams end up with the same number of goals at the end of N minutes) Since the number of ways can be very large, you need to print the answer mod 1000000007.

Note 1: Two ways are considered different, if the event(s) of at least 1 minute are different in them.

Note 2: For the sake of simplicity, you can assume that all the players in a team are identical.

Input

First line contains T, the number of test cases.

Each test case consists of a single line, with 2 space separated integers, N and M.

Output

For each test case, output a single line, containing the number of ways mod 1000000007.

Constraints

1 ≤ T ≤ 100

5 ≤ M ≤ 11

1 ≤ N ≤ 100

Example

Input:
2
1 11
2 8

Output:
3
11

Explanation

In the first test case, in the first minute, the occurrence of any of the events 3, 4 and 5 described in the problem can lead to a draw. Hence there are 3 ways for it to end in a draw.