Phân đoạn tín hiệu (Signal Partition)

Phiên bản: Phước Hưng OJ

Đề bài

Cho dãy $N$ số nguyên $A_1,A_2,\ldots,A_N$ thỏa $0\le A_i<2^{20}$.

Một đoạn liên tiếp $[L,R]$ được gọi là hợp lệ nếu XOR theo bit của các phần tử trong đoạn là một lũy thừa của $2$, tức thuộc tập

Trong bài toán này, $0$ không được coi là một lũy thừa của $2$.

Hãy đếm số cách chia toàn bộ dãy thành các đoạn liên tiếp không rỗng sao cho mọi đoạn đều hợp lệ. Hai cách chia khác nhau nếu vị trí đặt ít nhất một dấu cắt khác nhau.

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In ra số cách chia thỏa mãn, lấy modulo $1\,000\,000\,007$.

Subtask

• Subtask 1 (25%): $1\le N\le 25$, $0\le A_i<2^{20}$.
• Subtask 2 (25%): $1\le N\le 5000$, $0\le A_i<2^{20}$.
• Subtask 3 (50%): $1\le N\le 2\times10^5$, $0\le A_i<2^{20}$.

Ví dụ

Ví dụ 1

Input

3
1 2 1

Output

2

Giải thích

Hai cách hợp lệ là $[1][2][1]$ và $[1,2,1]$. Ở cách thứ hai, $1\oplus2\oplus1=2$.

Ví dụ 2

Input

2
3 3

Output

0

Giải thích

Cách chia $[3,3]$ có XOR bằng $0$ nên không hợp lệ. Cách $[3][3]$ cũng không hợp lệ vì $3$ không phải lũy thừa của $2$. Do đó đáp án bằng $0$.