题目描述

長さ $n$ の数列 $a$ の 美しさ を $a_1\ \oplus\ a_2\ \oplus\ \cdots\ \oplus\ a_{n}$ で定義します。ここで $\oplus$ はビットごとの排他的論理和を表します。

長さ $N$ の数列 $A$ が与えられます。 すぬけ君は $A$ に $0$ 個以上の仕切りを入れて、いくつかの空でない連続する部分列に分割しようとしています。

仕切りを入れる方法は $2^{N-1}$ 通りあります。 それらのうち、分割された数列たちの美しさが全て等しくなるものの個数を $10^{9}+7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\ldots$ $A_{N}$

输出格式

答えを出力せよ。

题目大意

给定长度为 $n$ 的数列，把这串数字划分成若干段，求使得每一段异或和都相等的方案数对 $10^9 + 7$ 取模后结果。

3
1 2 3

3

3
1 2 2

1

32
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

147483634

24
1 2 5 3 3 6 1 1 8 8 0 3 3 4 6 6 4 0 7 2 5 4 6 2

292

提示

制約

• 入力は全て整数
• $1\ \leq\ N\ \leq\ 5\ \times\ 10^5$
• $0\ \leq\ A_i\ <\ 2^{20}$

Sample Explanation 1

条件を満たす分割方法は以下の $3$ 通りです。$(1),(2),(3)$ と分割したときに限り、全ての美しさが等しくなりません。 - $(1,2,3)$ - $(1),(2,3)$ - $(1,2),(3)$

Sample Explanation 3

- 条件を満たすものの個数を $10^{9}+7$ で割ったあまりを求めてください。