Problem Statement

There is a tree whose vertices are labelled with either $0$ or $1$. The tree has $N$ vertices numbered $1$ through $N$. For each $i$, there is an edge connecting Vertex $a_i$ and Vertex $b_i$. The label of Vertex $i$ is $c_i$.

Snuke wants to repeat performing the following operation on the tree:

• Choose an edge, contract it, and label the new vertex with the NAND of the labels of two old vertices.

After performing $N - 1$ operations, the tree ends up with a single vertex. Among $(N-1)!$ ways to do so, how many will result in a vertex labelled with $1$? Compute the answer modulo $2$.

Note

• NAND operation is defined as follows: $NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0$.
• When we contract an edge between Vertex $s$ and Vertex $t$, we remove the edge, and simultaneously merge the two vertices. There is an edge between the merged vertex and Vertex $u$ in the new tree iff there is an edge between $s$ and $u$, or an edge between $t$ and $u$, in the old tree.

Constraints

• $2 \leq N \leq 300$
• $1 \leq a_i < b_i \leq N$
• The input represents a valid tree.
• $0 \leq c_i \leq 1$
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.