E - XOR Partitioning

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

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

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

仕切りを入れる方法は 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

Score : 800 points

Problem Statement

The beauty of a sequence a of length n is defined as a_1 \oplus \cdots \oplus a_n, where \oplus denotes the bitwise exclusive or (XOR).

You are given a sequence A of length N. Snuke will insert zero or more partitions in A to divide it into some number of non-empty contiguous subsequences.

There are 2^{N-1} possible ways to insert partitions. How many of them divide A into sequences whose beauties are all equal? Find this count modulo 10^{9}+7.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq A_i < 2^{20}

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_{N}

Output

Print the answer.


Sample Input 1

3
1 2 3

Sample Output 1

3

Four ways of dividing A shown below satisfy the condition. The condition is not satisfied only if A is divided into (1),(2),(3).

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

Sample Input 2

3
1 2 2

Sample Output 2

1

Sample Input 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

Sample Output 3

147483634

Find the count modulo 10^{9}+7.


Sample Input 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

Sample Output 4

292