Tree Partition Weight Sum

Given a tree with n nodes, where the i-th node has an integer weight \(x_i\). The tree has \(n-1\) edges. For each edge you can independently decide whether to delete it or not, hence there are \(2^{n-1}\) possible deletion schemes. For a fixed deletion scheme, let the resulting forest have connected components \(C_1, C_2, \dots, C_k\). Define the value of each component as the bitwise XOR of the node weights in that component, i.e., \[ v_i = \bigoplus_{u \in C_i} x_u, \quad 1 \le i \le k,\] and the weight of the scheme is defined as the product \[ W = v_1 \times v_2 \times \cdots \times v_k.\] Compute the sum of the weights of all \(2^{n-1}\) deletion schemes modulo \(998\,244\,353\).

Note: The symbol \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The first line contains a single integer \(n\) (the number of nodes).

The second line contains \(n\) integers \(x_1, x_2, \dots, x_n\) representing the weight of each node.

Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) (1-indexed) that describe an edge connecting node \(u\) and node \(v\).

outputFormat

Output a single integer: the sum of the weights of all deletion schemes modulo \(998\,244\,353\).

sample

2
1 2
1 2

5