题目描述

有一个树，其顶点上标有 $0$ 或 $1$。树有 $N$ 个顶点，编号从 $1$ 到 $N$。对于每个 $i$，有一条连接顶点 $a_i$ 和顶点 $b_i$ 的边。顶点 $i$ 的标记为 $c_i$。

Snuke 想要在树上重复执行以下操作：

• 选择一条边，合并它们，并用两个旧顶点的标签的 NAND 值标记新顶点。

执行 $N-1$ 次操作后，树会变成一个单独的顶点。在 $(N-1)!$ 种可能中，有多少种结果顶点标记为 $1$？将答案对 $2$ 取模。

注意事项

• NAND 操作定义如下：$NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0$。
• 当我们合并连接顶点 $s$ 和 $t$ 的边时，我们删除这条边，并同时合并这两个顶点。新树中，当且仅当旧树中有边连接 $s$ 和 $u$，或者连接 $t$ 和 $u$ 时，合并后的顶点和顶点 $u$ 之间存在一条边。

约束条件

• $2 \\leq N \\leq 300$
• $1 \\leq a_i < b_i \\leq N$
• 输入表示一棵有效的树。
• $0 \\leq c_i \\leq 1$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $c_2$ $\\cdots$ $c_N$

输出

打印答案。

示例输入 1

4
1 2
2 3
2 4
0 1 1 0

示例输出 1

0

在所有 $6$ 种可能的情况中，有 $4$ 种最终结果标记为 $1$，因此答案为 $4 \\ mod \\ 2 = 0$。

示例输入 2

4
1 2
2 3
3 4
1 1 0 1

示例输出 2

1

示例输入 3

20
3 15
1 12
10 16
3 19
5 20
1 9
6 13
14 19
2 4
8 11
12 16
6 20
2 17
16 18
17 19
7 10
16 20
2 20
8 20
1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0

示例输出 3

0