Meteorological Fixed Point

In a twisting storm the weather of celestial bodies is ever‐changing. In this problem, the roads in the storm form an unrooted tree with (n) nodes. Each node (i) is initially assigned a binary weight (w_i) (either 0 or 1) and a type (t_i). The type can be either an (\texttt{AND}) node or an (\texttt{OR}) node. The evolution of the weights is defined as follows:

• For an (\texttt{AND}) node, at the end of each second its new weight becomes [ a_i = w_i \land \bigwedge_{j\in N(i)} w_j, ] that is, the bitwise AND of its own previous weight and the previous weights of all its neighbors.

• For an (\texttt{OR}) node, at the end of each second its new weight becomes [ a_i = w_i \lor \bigvee_{j\in N(i)} w_j, ] that is, the bitwise OR of its own previous weight and the previous weights of all its neighbors.

Eventually, a time comes when the weights stop changing; denote the fixed weight of node (i) by (a_i). However, we do not know the initial weights (w_i) nor the node types (t_i); we are only given the final configuration (a_1, a_2, \dots, a_n).

Your task is to calculate the number of possible combinations of initial weights and type assignments that lead to the given fixed configuration, modulo (998244353).

Note that in the evolution process the update at each node is performed synchronously. In particular, if a node is of type (\texttt{AND}) and its fixed weight (a_i=1), then it must be that the initial weight of every node in its closed neighborhood ({i}\cup N(i)) was (1). Similarly, if a node is of type (\texttt{OR}) and its fixed weight (a_i=0), then the initial weight of every node in its closed neighborhood was (0). When the closed neighborhood is not uniform, the node’s new weight depends on the type: an (\texttt{AND}) node yields (0) while an (\texttt{OR}) node yields (1).

Formally, if we denote by (x_i) the initial weight of node (i) and assume the closed neighborhood of node (i) is (S_i = {i} \cup {j:\ (i,j) \text{ is an edge}}), then the evolution tells us that for every node (i):

• If (t_i=\texttt{AND}) then (a_i = \bigwedge_{j\in S_i} x_j); in particular, if (a_i=1) then (x_j=1) for all (j\in S_i).
• If (t_i=\texttt{OR}) then (a_i = \bigvee_{j\in S_i} x_j); in particular, if (a_i=0) then (x_j=0) for all (j\in S_i).

When (S_i) is not uniform (i.e. contains both 0 and 1), then an (\texttt{AND}) node outputs (0) (forcing (a_i=0)) and an (\texttt{OR}) node outputs (1) (forcing (a_i=1)).

Count the number of valid pairs (({x_i}, {t_i})) (with (x_i\in{0,1}) and (t_i\in{\texttt{AND},\texttt{OR}})) that give rise to the fixed configuration (a_1, a_2, \dots, a_n). Since the answer might be large, output it modulo (998244353).

inputFormat

The input begins with an integer (n) ((1\le n\le 2\cdot10^5)), the number of nodes in the tree.

The second line contains (n) space‐separated integers (a_1, a_2, \dots, a_n) (each either 0 or 1), representing the fixed weight of each node.

Each of the next (n-1) lines contains two integers (u) and (v) ((1\le u,v\le n,\ u\ne v)), indicating that there is an edge between nodes (u) and (v). It is guaranteed that these edges form a tree.

outputFormat

Output a single integer: the number of possible combinations of initial weights and type assignments that yield the given fixed configuration, modulo (998244353).

sample

1
1

2

</p>