I. 真相
time limit per test
1 s
memory limit per test
512 megabytes
input
standard input
output
standard output

有一棵包含 $$$n$$$ 个节点的有根树，其根节点为 1。每个节点上站着一个人，每个人要么是"诚实者"（总是说真话），要么是"说谎者"（总是说假话）。

现在，对于每个 $$$i \in [1,n]$$$，位于节点 $$$i$$$ 的人都说了一句话："以我所在的节点为根的子树中，恰好有 $$$a_i$$$ 个诚实者。"

一个"真假分配情况"是指为每个节点的人分配一个"诚实者"或"说谎者"的身份。你需要计算，有多少种可能的真假分配情况，能够满足以下逻辑自洽条件：

  • 对于任意一个节点 $$$i$$$，如果该节点的人是诚实者，那么他陈述的数字 $$$a_i$$$ 必须等于其子树中诚实者的实际总数。
  • 对于任意一个节点 $$$i$$$，如果该节点的人是说谎者，那么他陈述的数字 $$$a_i$$$ 必须不等于其子树中诚实者的实际总数。

gsh 对真相非常感兴趣，他想知道满足上述条件的真假分配情况总共有多少种。请输出答案对 $$$998244353$$$ 取模的结果。

Input

第一行输入一个整数 $$$T$$$（$$$1 \le T \le 5000$$$），表示数据组数。

接下来对每组数据输入如下：

  • 第一行输入一个正整数 $$$n$$$（$$$1 \le n \le 5000$$$，$$$\sum n \le 5000$$$），表示节点数量。
  • 第二行输入 $$$n$$$ 个以空格分开的非负整数 $$$a_i$$$（$$$0 \le a_i \le n$$$）。
  • 接下来的 $$$n-1$$$ 行，每行输入两个正整数 $$$u_i$$$，$$$v_i$$$，表示一条边。保证输入的边构成一棵树。
Output

对每组数据输出一行一个整数表示答案对 $$$998244353$$$ 取模后的结果。

Example
Input
6
3
1 2 3
1 2
1 3
3
0 2 3
1 2
1 3
3
0 2 1
1 2
1 3
5
5 1 1 1 4
5 1
4 5
5 3
2 5
5
5 1 3 4 1
5 3
2 3
1 4
4 3
6
3 5 1 0 1 0
2 6
4 5
2 3
6 1
4 2
Output
2
0
1
10
7
3
Note

对于第一组数据，有 $$$2$$$ 种可能：

  1. 1 号说真话，2 号说假话，3 号说假话。
  2. 1 号说假话，2 号说假话，3 号说假话。

对于第二组数据，没有合法方案。

对于第三组数据，只有唯一一种可能：1 号说假话，2 号说假话，3 号说真话。