Background

With Moon Island, the king crab, and the celestial detector, you have successfully assembled three pieces of celestial technology. Next, what you need to do is to reach the center of the Eye of the Storm and prepare for the final step of that mysterious experiment.

The ultimate truth is within reach. Can you pass this trial successfully?

Problem Description

The weather inside a celestial storm changes rapidly.

The roads in the storm form an unrooted tree with $n$ nodes. Node $i$ has an initial value $w_i$ ($w_i$ is $0$ or $1$) and a type $t_i$.

There are two types of nodes: $\texttt{AND}$ nodes and $\texttt{OR}$ nodes.

For an $\texttt{AND}$ node, after each second ends, its value becomes the $\texttt{AND}$ of its own value and the values of all its neighbors from the previous second.

For an $\texttt{OR}$ node, after each second ends, its value becomes the $\texttt{OR}$ of its own value and the values of all its neighbors from the previous second.

Now it is known that from some moment on, the values of all nodes no longer change. Call the value of node $i$ at this moment $a_i$.

You do not know the initial value and type of each node, and you only know the final value $a_i$ of each node. Find how many possible combinations of initial values and types there are. Output the answer modulo $998244353$.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

The second line contains $n$ integers $a_1, a_2, \ldots , a_n$, representing the final value of each node.

The next $n-1$ lines each contain two integers $x,y$, describing an edge in the unrooted tree.

Output Format

Output one line with one integer, the number of possible combinations of initial values and types.

2
0 0
1 2

6

Hint

[Sample 1 Explanation]

There are six possible combinations of initial values and types as follows:

1. $((w_1, t_1), (w_2, t_2)) = ((0, \texttt{AND}), (0, \texttt{AND}))$.

2. $((w_1, t_1), (w_2, t_2)) = ((0, \texttt{AND}), (0, \texttt{OR}))$.

3. $((w_1, t_1), (w_2, t_2)) = ((0, \texttt{OR}), (0, \texttt{AND}))$.

4. $((w_1, t_1), (w_2, t_2)) = ((0, \texttt{OR}), (0, \texttt{OR}))$.

5. $((w_1, t_1), (w_2, t_2)) = ((1, \texttt{AND}), (0, \texttt{AND}))$.

6. $((w_1, t_1), (w_2, t_2)) = ((0, \texttt{AND}), (1, \texttt{AND}))$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $2 \le n \le 2 \times {10}^5$, $1 \le x, y \le n$, $a_i \in \{ 0, 1 \}$, and the input is guaranteed to form a tree.

Translated by ChatGPT 5