配点 : $800$ 点

問題文

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

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

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

制約

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

入力

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

$N$

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

出力

答えを出力せよ。

3
1 2 3

3

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

• $(1,2,3)$
• $(1),(2,3)$
• $(1,2),(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

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

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