## Max Split

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