Max Split

Points: 100
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Python

You are given a binary trees $$T$$ with $$N$$ nodes.

Split the $$T$$ into two trees $$T_1$$ and $$T_2$$ by removing any edge, such that product of sum of values on $$T_1$$ and $$T_2$$ is maximum.

Output the maximum product modulo $$10^9 + 7$$.

Input

First line contains single integer: $$N$$.

Following lines of input describe the $$T$$.

First line contains single integer : $$root$$

Next line contains $$N$$ integers, where $$i^{th}$$ integer is the value of the node with index $$i$$.

Next $$N$$ lines contains two integers each, index of left child and right child of node with index $$i$$. If any of integer is $$-1$$ then corresponding child is absent.

Output

Output the maximum product modulo $$10^9 + 7$$.

Constraints

$$2$$ $$\leq$$ $$N$$ $$\leq$$ $$10^5$$

$$0 \leq value[i] \leq 10^9$$

Example

Input

3
1
1 2 3
2 3
-1 -1
-1 -1

Output

9

Remove the edge $$[1,3]$$ , required product will be $$3 \times (1 + 2) = 9$$.

Note

You can use this template to submit the solution.

Comments

There are no comments at the moment.