Barcelona Gameplay Tactics

All submissions for this problem are available.
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 counterattack 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 counterstrike 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 counterattack :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 counterattack and the coach, Tito Villanova knows that this counterattack 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 spacesparated 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  Messi
2) Messi  Busquets  Messi
3) Messi  Iniesta  Messi
4) 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  Messi
2) Messi  Xavi  Iniesta  Xavi  Messi
3) Messi  Xavi  Messi  Xavi  Messi
4) Messi  Iniesta  Messi  Iniesta  Messi
5) Messi  Iniesta  Messi  Xavi  Messi
6) Messi  Iniesta  Xavi  Iniesta  Messi
Author:  kuruma 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/FCBARCA 
Tags  april13, dynamicprogramming, kuruma, simple, simplemath 
Date Added:  28102012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 