题目背景

通过月岛，帝王蟹和天体探测仪，你成功拼合了三个天体科技，接下来你要做的，就是来到风暴之眼的中心，准备那个神秘实验的最后一步。

最终的真相近在咫尺，你能否成功通过这场考验呢？

题目描述

天体风暴中的气象瞬息万变。

风暴中的道路构成一棵 $n$ 个结点的无根树，第 $i$ 个结点有初始权值 $w_i$（$w_i$ 为 $0$ 或 $1$）和类型 $t_i$。

结点的类型分为两种：$\texttt{AND}$ 型结点和 $\texttt{OR}$ 型结点。

对于 $\texttt{AND}$ 型结点，每一秒结束后它的权值将变为它与它所有邻居上一秒权值的 $\texttt{AND}$ 和；

对于 $\texttt{OR}$ 型结点，每一秒结束后它的权值将变为它与它所有邻居上一秒权值的 $\texttt{OR}$ 和。

现在，已知从某一时刻起，所有结点的权值都不再发生任何变化，将此时点 $i$ 的权值称为 $a_i$。

现不知每个点的初始权值和类型，只知道最终每个点的权值 $a_i$，求出有多少种可能的初始权值和类型的组合，答案对 $998244353$ 取模。

输入格式

第一行，一个整数 $n$，表示树的结点数。

第二行，$n$ 个整数 $a_1, a_2, \ldots , a_n$，表示每个结点最终的权值。

接下来 $n-1$ 行，每行两个整数 $x,y$，描述无根树中的一条边。

输出格式

输出一行一个整数，表示可能的初始权值和类型的组合数量。

2
0 0
1 2

6

提示

【样例 1 解释】

有如下六种初始权值和类型的组合：

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}))$。

---

【数据范围】

本题采用捆绑测试。

对于 $100 \%$ 的数据，$2 \le n \le 2 \times {10}^5$，$1 \le x, y \le n$，$a_i \in \{ 0, 1 \}$，保证输入构成一棵树。

子任务编号	分值	$n\leq$	特殊限制
$1$	$10$		无
$2$	$22$	$20$
$3$		$1000$
$4$	$11$	${10}^5$	$y=x+1$
$5$	$15$		$a_i=0$
$6$	$20$	$2 \times {10}^5$	无

---