/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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}
出力
答えを出力せよ。
入力例 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