You are given a tree $G$ with $N$ nodes rooted at node $1$. We need to assign values to each node as follows:-

• The value of each node can be any positive integer up to $X$.
• The value of a child node is less than or equal to its parent node.

Find the number of valid assignments that are possible for a given tree $G$ . Since this number can be very large, print it modulo $10^9 + 7$.

Two assignments are said to be different if there exists at least one node with different values assigned.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $N \ X$ denoting the number of nodes in the tree and the value of $X$ respectively.
• Next $N - 1$ lines contain two space-separated integer $u \ v$, denoting an edge between node $u$ and node $v$.

Output format

For each test case in a new line, print the number of valid assignments modulo $10^9 + 7$.

Constraints

$1 \le T \le 10 \\ 2 \le N \le 10^3 \\ 1 \le X \le 10^9$