Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] 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 ≤ N ≤ 10^{5}$
$0 ≤ x ≤ 10^{9}$
$0 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ u, v ≤ N$

------ Subtasks ------
Subtask #1 (10 points): $N ≤ 100$

Subtask #2 (20 points): $N ≤ 5,000$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------
7 1
1 0 1 0 1 0 1
1 2
1 3
2 4
2 5
3 6
3 7
----- Sample Output 1 ------
5
----- explanation 1 ------
There are five valid ways to remove edges, splitting the tree into subtrees on nodes:
- [1, 2, 3, 4, 5, 6] and [7] by removing the edge (3-7)
- [1, 2, 3, 4, 6, 7] and [5] by removing the edge (2-5)
- [2, 4, 5] and [1, 3, 6, 7] by removing the edge (1-2)
- [2, 4, 5], [1], [3,6] and [7] by removing edges (1-2), (1-3) and (3-7)
- [1, 2, 4], [5], [3,6] and [7] by removing edges (2-5), (1-3) and (3-7)

见题面

见题面