You have a tree consisting of n vertices. You want to color each vertex of the tree in one of the k colors such that for any pair of vertices having same color, all the vertices belonging to the path joining them should also have same color. In other words, for any two vertices u, v with same color, all the vertices in the path joining them should also have color same as that of the u (or same as v, as u and v have same color). 

Find out possible number of ways in which you can color the tree satisfying the above property. As the answer could be large, print your answer modulo 109 + 7.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
For each test case, first line contains two space separated integers n, k denoting number of vertices in the tree and total number of colors, respectively
Each of the next n - 1 lines contain two space separated integers ui, vi, denoting that there is an edge between vertices ui and vi in the tree.

-----Output-----
For each test case, output a single line corresponding to number of ways of coloring the tree.

-----Constraints-----
- 1 ≤ T ≤ 50
- 1 ≤ n, k ≤ 50
- 1 ≤ ui, vi ≤ n
- ui ≠ vi

-----Example-----
Input
3
3 2
1 2
2 3
3 1
1 2
2 3
4 3
1 2
2 3
2 4

Output:
6
1
39

-----Explanation-----
In the first example, You can color the vertices in the following 6 ways - {1, 1, 1}, {2, 2, 2}, {1, 2, 2}, {1, 1, 2}, {2, 1, 1}, {2, 2, 1}. Note that you can't color the tree in {1, 2, 1} as the vertices in the path connecting vertex 1 and 3, (i.e. 1, 2, 3) don't have same color. You can see that the color of 2nd vertex is not same as that of 1st and 3rd.
In the second example, Only possible coloring you can do is to color all the vertices with color 1.

```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=1000000007\nfact=[1]\nfor i in range(1,200):\n fact.append((fact[-1]*i)%mod)\ndef ncr(n,r):\n if n<r:\n  return 0\n return (((fact[n]*pow(fact[n-r],mod-2,mod))%mod)*pow(fact[r],mod-2,mod))%mod\n\nfor _ in range(eval(input())):\n n,k=list(map(int,input().split()))\n for i in range(n-1):\n  u,v=list(map(int,input().split()))\n res=0\n for i in range(1,k+1):\n  res+=(((ncr(k,i)*ncr(n-1,i-1))%mod)*fact[i])%mod\n  res%=mod\n print(res)\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 25039