問題文

長さ $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}$

出力

答えを出力せよ。

入力例 1

3
1 2 3

出力例 1

3

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

• $(1,2,3)$
• $(1),(2,3)$
• $(1,2),(3)$

入力例 2

3
1 2 2

出力例 2

1

入力例 3

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

出力例 3

147483634

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

入力例 4

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

出力例 4

292