Một dãy số ~a_1, a_2, ..., a_m~ (~m \ge 1~) được gọi là dãy đẹp nếu:

• ~a_1 < a_2 < ... < a_m~;
• Định nghĩa dãy ~b~ như sau: ~b_1 = a_1~ và ~b_i = b_{i-1} \oplus a_i \forall 1 < i \le m~, trong đó ~ \oplus ~ là phép XOR; thì điều kiện ~b_1 < b_2 < ... < b_m~ phải được thỏa mãn.

Cho một cây gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~, đỉnh thứ ~i~ có nhãn ~a_i~. Gọi ~P(u, v)~ là tập các cạnh trên đường đi đơn từ ~u~ đến ~v~ trên cây.

Một hành trình hợp lệ trên cây có thể được biểu diễn bằng dãy đỉnh ~x_1, x_2, ..., x_k~ (~k \ge 1~) thỏa mãn điều kiện:

• ~1 \le x_i \le n, \forall 1 \le i \le k~ và các đỉnh ~x_i~ đôi một phân biệt;
• Các tập cạnh ~P(x_1, x_2), P(x_2, x_3), ..., P(x_{k-1}, x_k)~ đôi một không giao nhau;
• Dãy ~a_{x_1}, a_{x_2}, ..., a_{x_k}~ là dãy đẹp.

Yêu cầu: Hãy đếm số hành trình hợp lệ trên cây đã cho.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) là số đỉnh của cây.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) biểu diễn nhãn của các đỉnh.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u, v~ (~1 \le u, v \le n~) biểu diễn một cạnh của cây.

Output

• Gồm một số nguyên duy nhất là số hành trình hợp lệ trên cây đã cho. Vì kết quả có thể rất lớn nên chỉ cần đưa ra phần dư khi chia kết quả cho ~10^9 + 7~.

Sample Input 1

3
1 2 3
1 2
2 3

Sample Output 1

5

Giải thích

Các hành trình hợp lệ là:

1. 1;
2. 2;
3. 3;
4. 1, 2;
5. 1, 3.

Subtasks