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\)