问题描述

对于一个长度为 $n$ 的序列 $a$，其 美丽值 被定义为 $a_1 \\oplus \\cdots \\oplus a_n$，其中 $\\oplus$ 表示按位异或（XOR）。

给定长度为 $N$ 的序列 $A$。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$ 被分割为 $(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