An undirected connected graph $G$ has $n$ vertices and $n-1$ edges. The vertices are numbered from $1$ to $n$, and the weight of vertex $i$ is $W_i$. Each edge has a length of $1$. The distance between two vertices $(u, v)$ in the graph is defined as the shortest distance between them. For any pair of vertices $(u, v)$ in graph $G$, if their distance is $2$, they produce a joint weight of $W_u \times W_v$.

Find the maximum joint weight among all ordered pairs of vertices in graph $G$ that produce a joint weight, and the sum of all such joint weights.

Input

The first line contains an integer $n$.

The next $n-1$ lines each contain two space-separated positive integers $u$ and $v$, representing an edge between vertex $u$ and vertex $v$.

The last line contains $n$ positive integers, separated by spaces, where the $i$-th integer represents the weight $W_i$ of vertex $i$ in graph $G$.

Output

Output a single line containing two integers separated by a space: the maximum joint weight and the sum of all joint weights in graph $G$. Since the sum of all joint weights may be very large, output it modulo $10007$. It is guaranteed that there exists at least one ordered pair of vertices that produces a joint weight.

Examples

Input 1

5
1 2
2 3
3 4
4 5
1 5 2 3 10

Output 1

20 74

Note

The graph for this example is shown above. The ordered pairs with a distance of $2$ are $(1,3), (2,4), (3,1), (3,5), (4,2), (5,3)$. Their joint weights are $2, 15, 2, 20, 15, 20$, respectively. The maximum is $20$, and the total sum is $74$.

Constraints

For 30% of the data, $1 < n \leq 100$.

For 60% of the data, $1 < n \leq 2000$.

For 100% of the data, $1 < n \leq 200000, 0 < W_i \leq 10000$.