You are given a tree that is rooted at 1 and contains N nodes. Each node u has a value assigned to it that is denoted as Valu. A subset of nodes is selected in a random manner. Any node can be selected with equal probability.
The value of the subset is defined as follows:
Let the lowest common ancestor of these nodes be L. If ValL is greater than Valu for all u belonging to this subset, then the score of this subset is u. Otherwise, the score is 1. For an empty subset, the score is 0.
You must determine the expected score of the subset. The answer can be represented as PQ.
Print the answer as P⋅Q−1 modulo 109+7.
Input format
- First line: A single integer N denoting the total number of nodes in the tree
- Next N−1 lines: Two space-separated integers u and v denoting an edge between u and v
- Next line: N space-separated integers where the ith integer denotes Vali
Output format
Print the required value modulo 109+7 .
Constraints
2≤N≤2000001≤u, v≤N1≤Vali≤200000
Consider all the subsets:
{} - > Score = 0 for empty subset
{1} -> Lca = 1, Score = 1 , because value of node 1 is not less than that of lca, Score of subset is 1.
{2} -> Lca = 2, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{3} -> Lca = 3, Score = 1, because value of node 3 is not less than that of lca, Score of subset is 1.
{4} -> Lca = 4, Score = 1, because value of node 4 is not less than that of lca, Score of subset is 1.
{1,2} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{1,3} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{1,4} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{2,3} -> Lca = 2, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{2,4} -> Lca = 1, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{3,4} -> Lca = 1, Score = 1, because value of both nodes is less than that of lca, Score of subset is equal to that of lca which is 1 in this case.
{1,2,3} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{1,2,4} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
{2,3,4} -> Lca = 1, Score = 1, because value of node 2 is not less than that of lca, Score of subset is 1.
{1,2,3,4} -> Lca = 1, Score = 1, because value of node 1 is not less than that of lca, Score of subset is 1.
Hence, the expected value is 1516.
