Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

B. Colored Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an undirected tree on $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Each vertex $$$v$$$ has an initial color $$$a_v$$$. You perform a uniformly random permutation of the colors $$$\{a_1, a_2, \dots, a_n\}$$$ over the $$$n$$$ vertices (all $$$n!$$$ permutations are considered different from each other).

After shuffling, define $$${ D = max_{\substack{u, \space v \space \in \{1, \space\space 2, \space\space \dots, \space\space \large{n}\} \\ a_u \neq a_v}} \mathrm{dist}(u,v). }$$$

where $$$\mathrm{dist}(u,v)$$$ is the number of edges on the unique simple path between $$$u$$$ and $$$v$$$. In other words, $$$D$$$ is the maximum distance between any two vertices that end up with different colors. If all the vertices are of the same color then $$$D$$$ is equal to $$$0$$$.

Since $$$\mathbb{E}[D]$$$ is a rational number $$$\frac{P}{Q}$$$ (with $$$Q$$$ coprime to $$$10^9 + 7$$$), output the value of $$$P \cdot Q^{-1} \bmod 10^9 + 7$$$, where $$$Q^{-1}$$$ denotes the modular inverse of $$$Q$$$ modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of testcases.

Each test case is described by:

  • A line with an integer $$$n$$$ ($$$1 \le n \le 5\times 10^5$$$) — the number of vertices.
  • $$$n-1$$$ lines, each with two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) — denoting an edge of the tree.
  • A line with $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le n)$$$ — the colors of the vertices (arbitrary integers; equal integers denote equal colors).

It is guaranteed that the sum of $$$n$$$ overall testcases does not exceed $$$5\times 10^5$$$.

Output

For each test case, print a single integer — the expected value of $$$D$$$ after a uniformly random shuffle of the colors, taken modulo $$$10^9+7$$$.

Example
Input
1
8
3 5
1 4
2 5
7 8
2 8
2 4
6 8
7 4 5 1 2 1 3 1
Output
4