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.

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.

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.

Sample Input 1

4
1 2
2 3
2 4
0 1 1 0

Sample Output 1

0

It turns out that in 4 of all 6 ways the final label will be 1, so the answer is 4 \ mod \ 2 = 0.

Sample Input 2

4
1 2
2 3
3 4
1 1 0 1

Sample Output 2

1

Sample Input 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

Sample Output 3

0

见题面 Input 部分

见题面 Output 部分