You are given binary tree, having integral (greater than 0) node values. Find the number of paths having bitwise XOR of all its node values 0.

For example, this binary tree has 2 paths(undirected) having Bitwise XOR as 0.

(3)-(6)-(4)-(1) and (87)-(1)-(86)

Note: Bitwise XOR is operation represented by ‘^’ on keyboard. Binary tree has nodes having at most 2 children.

INPUT FORMAT:

First line inputs n, number of nodes in Binary Tree.

Second line contains n integers, Array A representing node values.

Next n-1 lines input undirected edges between diff nodes. It is guaranteed that the edges form a Binary Tree.

OUTPUT FORMAT:

Output single value, the number of paths having XOR of all values (of nodes) as 0.

CONSTRAINTS:

1 <= n <= 10^5

1 <= A[i] <= 127

SAMPLE INPUT:

6

4 6 1 3 87 86

0 1

1 3

0 2

2 4

2 5

SAMPLE OUTPUT:

As Explained above.