As we all know, F.C. Barcelona is the best soccer team of our era! Their entangling and mesmerizing game style usually translates into very high ball possession, consecutive counter-attack plays and goals. Lots of goals, thanks to the natural talent of their attacker and best player in history, Lionel Andres Messi.
However, at the most prestigious tournament of individual teams, the UEFA Champions League, there are no guarantees and believe it or not, Barcelona is in trouble.... They are tied versus Chelsea, which is a very defending team that usually relies on counter-strike to catch opposing teams off guard and we are in the last minute of the match. So Messi decided to settle things down for good and now he is conducting the ball on his teams' midfield and he will start a lethal counter-attack :D
After dribbling the 2 strikers from Chelsea, he now finds himself near the center of the field and he won't be able to dribble the entire team on his own, so he will need to pass the ball to one of his teammates, run forward and receive the ball once again to score the final goal.
Exactly K players are with him on his counter-attack and the coach, Tito Villanova knows that this counter-attack will end in a goal only if after exactly N passes are performed between the players, Messi ends up with the ball.
(Note that the ball only needs to end with Messi after exactly N passes are performed between all the K+1 players, i.e. Messi can receive the ball several times during the N passes. See the 2nd test case explanation for further clarification. )
However, he realized that there are many scenarios possible for this, so he asked you, his assistant coach, to tell him in how many ways can Messi score the important victory goal. So help him!!

Input
Input will contain a number T denoting the number of test cases.
Then T test cases follow, each one consisting of two space-sparated integers N and K.

Output
For each test case, output a single integer, the number of ways the winning play might happen modulo 1000000007 (10^9+7).

Constraints

1 ≤ T ≤ 100
2 ≤ N ≤ 1000
1 ≤ K ≤ 10

Example

Input:
2
2 4
4 2

Output:
4
6

Explanation
In the first test case, say four players with Messi are Xavi, Busquets, Iniesta and Jordi Alba. Then the ways of the winning play to happen when exactly 2 passes are to be performed are:1) Messi - Xavi - Messi2) Messi - Busquets - Messi3) Messi - Iniesta - Messi4) Messi - Alba - Messi
In the second test case, also say that two players with Messi are Xavi and Iniesta. There are 6 ways for the winning play to happen when exactly 4 passes are performed. All the examples of such winning play are:1) Messi - Xavi - Messi - Iniesta - Messi2) Messi - Xavi - Iniesta - Xavi - Messi3) Messi - Xavi - Messi - Xavi - Messi4) Messi - Iniesta - Messi - Iniesta - Messi5) Messi - Iniesta - Messi - Xavi - Messi6) Messi - Iniesta - Xavi - Iniesta - Messi

见题面

见题面