{"raw_statement":[{"iden":"problem statement","content":"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$.\nSnuke wants to repeat performing the following operation on the tree:\n\n*   Choose an edge, contract it, and label the new vertex with the NAND of the labels of two old vertices.\n\n![image](https://img.atcoder.jp/agc050/6fd816a993f20325edb625c93745ee8f.png)\nAfter 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$**."},{"iden":"notes","content":"*   NAND operation is defined as follows: $NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0$.\n*   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."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 300$\n*   $1 \\leq a_i < b_i \\leq N$\n*   The input represents a valid tree.\n*   $0 \\leq c_i \\leq 1$\n*   All values in the input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$:$\n$a_{N-1}$ $b_{N-1}$\n$c_1$ $c_2$ $\\cdots$ $c_N$"},{"iden":"sample input 1","content":"4\n1 2\n2 3\n2 4\n0 1 1 0"},{"iden":"sample output 1","content":"0\n\nIt turns out that in $4$ of all $6$ ways the final label will be $1$, so the answer is $4 \\ mod \\ 2 = 0$."},{"iden":"sample input 2","content":"4\n1 2\n2 3\n3 4\n1 1 0 1"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"20\n3 15\n1 12\n10 16\n3 19\n5 20\n1 9\n6 13\n14 19\n2 4\n8 11\n12 16\n6 20\n2 17\n16 18\n17 19\n7 10\n16 20\n2 20\n8 20\n1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0"},{"iden":"sample output 3","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}