All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB19TST/hindi/XDCOMP.pdf), [Bengali](http://www.codechef.com/download/translated/FEB19TST/bengali/XDCOMP.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB19TST/mandarin/XDCOMP.pdf), [Russian](http://www.codechef.com/download/translated/FEB19TST/russian/XDCOMP.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB19TST/vietnamese/XDCOMP.pdf) as well. Chef has a tree with $N$ nodes (numbered $1$ through $N$) and a non-negative integer $x$. The nodes of the tree have non-negative integer weights; let's denote the weight of node $i$ by $a_i$. Next, let's define the *XOR value* of a tree as the bitwise XOR of weights of all its nodes. Chef wants to remove zero or more edges from his tree in such a way that each individual tree in the forest formed by removing these edges has XOR value $x$. Help him compute the number of ways to remove a set of edges such that this condition is satisfied. Since the answer may be large, compute it modulo $10^9+7$. ### Input - The first line of the input contains two space-separated integers $N$ and $x$. - The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$. - Each of the following $N-1$ lines contains two space-separated integers $u$ and $v$ denoting an edge between nodes $u$ and $v$ in Chef's tree. ### Output Print a single line containing one integer ― the number of ways to remove edges, modulo $10^9+7$. ### Constraints - $1 \le N \le 10^5$ - $0 \le x \le 10^9$ - $0 \le a_i \le 10^9$ for each valid $i$ - $1 \le u, v \le N$ ### Subtasks **Subtask #1 (10 points):** $N \le 100$ **Subtask #2 (20 points):** $N \le 5,000$ **Subtask #3 (70 points):** original constraints ### Example Input ``` 7 1 1 0 1 0 1 0 1 1 2 1 3 2 4 2 5 3 6 3 7 ``` ### Example Output ``` 5 ``` ### Explanation There are five valid ways to remove edges, splitting the tree into subtrees on nodes: - [1, 2, 3, 4, 5, 6] and  by removing the edge (3-7) - [1, 2, 3, 4, 6, 7] and  by removing the edge (2-5) - [2, 4, 5] and [1, 3, 6, 7] by removing the edge (1-2) - [2, 4, 5], , [3,6] and  by removing edges (1-2), (1-3) and (3-7) - [1, 2, 4], , [3,6] and  by removing edges (2-5), (1-3) and (3-7)
|Tags||combinatorics, feb19, medium, observations, stevens, tree-dp|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.