Cho mảng ~a~ độ dài ~n~, các phần tử được đánh số từ ~1~ đến ~n~. Bạn hãy đếm số cách chia mảng ~a~ thành các mảng con liên tiếp không rỗng sao cho ~xor~ của các phần tử trong mỗi mảng con đều bằng nhau.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 5 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên của mảng ~a~ ~(0 \le a_i < 2^{20})~.

Output

• In ra số cách chia mảng ~a~ thành các mảng con thỏa mãn, kết quả chia lấy dư cho ~10^9+7~.

Examples

Sample Input 1

3
3 4 7

Sample Output 1

3

Sample Input 2

5
0 0 0 0 0

Sample Output 2

16

Notes

Trong ví dụ đầu tiên, có tổng cộng ~3~ cách chia mảng phù hợp:

1. ~(3,4,7)~
2. ~(3)~, ~(4,7)~
3. ~(3,4)~, ~(7)~