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)

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Graph algorithms


Solutions:
(q, x) = [int(i) for i in input().split()]
tree = []

def dfs(i, p, x):
	Z = [[a[i], 1]]
	Y = []
	for j in tree[i]:
		if j != p:
			Y.append(dfs(j, i, x))
	for sub in Y:
		temp = []
		for y in sub:
			for m in Z:
				flag = True
				flag0 = True
				if y[0] == x:
					for o in temp:
						if o[0] == m[0]:
							o[1] += y[1] * m[1]
							flag0 = False
					if flag0:
						temp.append([m[0], y[1] * m[1]])
				for o in temp:
					if o[0] == y[0] ^ m[0]:
						o[1] += y[1] * m[1]
						flag = False
						break
				if flag:
					temp.append([y[0] ^ m[0], y[1] * m[1]])
		Z = temp
	return Z
for _ in range(q):
	tree.append([])
a = [int(i) for i in input().split()]
for i in range(q - 1):
	(u, v) = [int(i) for i in input().split()]
	tree[u - 1].append(v - 1)
	tree[v - 1].append(u - 1)
ans = 0
Z = dfs(0, -1, x)
for m in Z:
	if m[0] == x:
		ans = m[1]
		break
print(ans % (10 ** 9 + 7))


import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int, input().split()))

def num():
	return map(int, input().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
dp = 0
mm = 1000000007
tree = 0
visited = 0
n = 0
x = 0
a = 0
b = 0

def solve():
	t = 1
	for it in range(t):
		global n, x, a, b, visited
		(n, x) = num()
		global dp
		visited = [False] * n
		dp = [0] * (n + 1)
		for i in range(n):
			dp[i] = [0] * 2
		a = [0] * n
		b = [0] * n
		a = li()
		global tree
		tree = [0] * (n + 1)
		for i in range(n + 1):
			tree[i] = []
		for i in range(n - 1):
			(u, v) = num()
			u = u - 1
			v = v - 1
			tree[u].append(v)
			tree[v].append(u)
		find(0)
		visited = [False] * n
		dfs(0)
		xy = 0
		if b[0] == 0:
			xy = dp[0][0]
		if b[0] == x:
			xy = (xy + dp[0][1]) % mm
		print(xy)

def dfs(xp):
	global visited, tree, b, a, dp, x
	visited[xp] = True
	m = 1
	n = 0
	for u in tree[xp]:
		if visited[u] == False:
			dfs(u)
			old1 = m
			old2 = n
			m = (old2 * dp[u][0] % mm + old1 * dp[u][1] % mm) % mm
			if x == b[u]:
				m = (m + dp[u][1] * old2 % mm) % mm
			if b[u] == 0:
				m = (m + dp[u][0] * old1 % mm) % mm
			n = (dp[u][0] * old1 % mm + dp[u][1] * old2 % mm) % mm
			if b[u] == 0:
				n = (n + dp[u][0] * old2 % mm) % mm
			if x == b[u]:
				n = (n + dp[u][1] * old1 % mm) % mm
	dp[xp][1] = m
	dp[xp][0] = n

def find(xp):
	global visited, tree, b, a
	visited[xp] = True
	for u in tree[xp]:
		if visited[u] == False:
			find(u)
			b[xp] = b[xp] ^ b[u]
	b[xp] = b[xp] ^ a[xp]
solve()


from collections import defaultdict
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)
M = int(10 ** 9 + 7)

def merge(cur, child):
	a_x = xor_list[child][x]
	B = Counter()
	for (k1, v1) in xor_list[cur].items():
		for (k2, v2) in xor_list[child].items():
			tmp = v1 * v2 % M
			B[k1 ^ k2] = (B[k1 ^ k2] + tmp) % M
	for (k, v) in xor_list[cur].items():
		B[k] = (B[k] + v * a_x % M) % M
	B = {k: v for (k, v) in B.items() if v != 0}
	return Counter(B)

def dfs(cur, parent):
	for el in tree[cur]:
		if el == parent:
			continue
		dfs(el, cur)
	for el in tree[cur]:
		if el == parent:
			continue
		xor_list[cur] = merge(cur, el)
(n, x) = map(int, input().split())
A = list(map(int, input().split()))
tree = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	tree[u].append(v)
	tree[v].append(u)
xor_list = [Counter() for i in range(n)]
for i in range(n):
	xor_list[i][A[i]] = 1
dfs(0, -1)
print(xor_list[0][x])


from sys import stdin, stdout
mod = 10 ** 9 + 7
(N, x) = [int(v) for v in stdin.readline().split()]
a = [None] + [int(v) for v in stdin.readline().split()]
neighbors = [None] + [[] for i in range(N)]
for edge in range(N - 1):
	(u, v) = [int(v) for v in stdin.readline().split()]
	neighbors[v].append(u)
	neighbors[u].append(v)

def solve_0(node, father=-1):
	data = [solve_0(child, node) for child in neighbors[node] if child != father]
	if len(data) == 0:
		return (a[node], 0)
	v = a[node]
	s = 0
	for (v1, s1) in data:
		v ^= v1
		s += s1 + (v1 == 0)
	return (v, s)

def solve(node, father=-1):
	data = [solve(child, node) for child in neighbors[node] if child != father]
	if len(data) == 0:
		return (a[node], 1, 0)
	v = data[0][0]
	s = data[0][1]
	c = data[0][2]
	s_bar = (s + (v == 0) * c) % mod
	c_bar = (c + (v == x) * s) % mod
	for (v1, s1, c1) in data[1:]:
		s1_bar = (s1 + (v1 == 0) * c1) % mod
		c1_bar = (c1 + (v1 == x) * s1) % mod
		v ^= v1
		(s_bar, c_bar) = [s_bar * s1_bar + c_bar * c1_bar, s_bar * c1_bar + s1_bar * c_bar]
	return (v ^ a[node], s_bar % mod, c_bar % mod)
if x == 0:
	(v, s) = solve_0(1)
	if v == 0:
		print(pow(2, s, mod))
	else:
		print(0)
else:
	(v, s, c) = solve(1)
	if v == x:
		print(s)
	elif v == 0:
		print(c)
	else:
		print(0)