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 (109+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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'mod = int(1e9+7)\n\nfor _ in range(int(input())):\n n, k = map(int, input().split())\n ls = [0] * (n + 1)\n ls[0], ls[1] = 1, 0\n for i in range(2, n+1):\n  ls[i] = ((k-1) * ls[i-1] + k * ls[i-2]) % mod\n print(ls[n])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13115