Connected Subtree Weights Sum

You are given a tree with n nodes. Each node v has an integer weight a_v. A connected subgraph (or connected subtree) is defined as a nonempty subset S of nodes such that the nodes in S induce a connected subgraph of the tree. The weight of a connected subgraph S is defined as

[ w(S)=\prod_{v\in S}\Bigl(a_v+|S|\Bigr), ]

where |S| denotes the number of nodes in S. Your task is to compute the sum of weights of all connected subgraphs modulo \(U^V\), i.e.,

[ \text{Answer} = \left(\sum_{S \text{ is connected}} w(S)\right) \bmod U^V. ]

Note: The tree is undirected and connected.

inputFormat

The first line contains an integer n (1 ≤ n ≤ small) indicating the number of nodes in the tree.

The second line contains n space-separated integers a₁, a₂, ..., a_n where a_i is the weight of the i-th node.

The next n-1 lines each contain two integers u and v (1 ≤ u, v ≤ n) which denote an edge connecting nodes u and v.

The last line contains two integers U and V. You are to compute the answer modulo \(U^V\).

You may assume that the tree is connected and that the input values are such that a brute force solution using bitmask enumeration over all connected subgraphs is feasible.

outputFormat

Output a single integer which is the sum of the weights of all connected subgraphs modulo \(U^V\).

sample

1
5
2 3

6