← 返回题目列表

AtCoder · diverta2019_e

E. 异或分区

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

的 美女 一个序列的 a 长度 n 定义为 a_1 \oplus \cdots \oplus a_n,其中 \oplus 表示按位异或(XOR)。

给你一个序列 A 长度 N。 Snuke 将在其中插入零个或多个分区 A 将其划分为一定数量的非空连续子序列。

有 2^{N-1} 插入分区的可能方法。 其中有多少人分 A 进入美丽都是平等的序列?求这个计数的模数 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

四种划分方式 下面显示的 A 满足条件。仅当以下情况时,条件才满足 A 分为 (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