题目描述

你和你的朋友正在玩一款构筑牌组的游戏。有 $N$ 张卡牌，编号从 $1$ 到 $N$。第 $i$ 张卡牌的数值为 $A_i$。

你需要为你和你的朋友各自构建一个牌组。一张卡牌不能同时出现在两个牌组中，也可以选择不使用所有 $N$ 张卡牌。允许某个牌组为空，即不包含任何卡牌。

一个牌组的“力量”定义为该牌组中所有卡牌数值的按位异或（XOR）结果。空牌组的力量为 $0$。

如果两个牌组的力量相等，则认为这局游戏是平衡的。

请你计算有多少种不同的方法可以构建两个牌组，使得游戏平衡。只要有一个牌组包含至少一张不同的卡牌，就认为两种方法不同。由于答案可能很大，请输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 100\,000$）。

第二行包含 $N$ 个整数 $A_i$（$1 \le A_i \le 100\,000$）。

输出格式

输出一个整数，表示可以使游戏平衡的构建方法数。答案对 $998\,244\,353$ 取模。

4
16 12 4 8

9

4
1 2 4 8

1

2
1 1

5

6
1 1 1 2 2 2

169

提示

样例输入输出 1 说明

设 $S$ 和 $T$ 分别为你和你朋友的牌组。共有 $9$ 种方法可以使游戏平衡。

• $S = \{\}$，$T = \{\}$。两个牌组的力量均为 $0$。
• $S = \{2, 3, 4\}$，$T = \{\}$。两个牌组的力量均为 $0$。
• $S = \{\}$，$T = \{2, 3, 4\}$。两个牌组的力量均为 $0$。
• $S = \{2, 4\}$，$T = \{3\}$。两个牌组的力量均为 $4$。
• $S = \{3\}$，$T = \{2, 4\}$。两个牌组的力量均为 $4$。
• $S = \{2, 3\}$，$T = \{4\}$。两个牌组的力量均为 $8$。
• $S = \{4\}$，$T = \{2, 3\}$。两个牌组的力量均为 $8$。
• $S = \{3, 4\}$，$T = \{2\}$。两个牌组的力量均为 $12$。
• $S = \{2\}$，$T = \{3, 4\}$。两个牌组的力量均为 $12$。

样例输入输出 2 说明

唯一能使游戏平衡的方法是两个牌组都为空。

样例输入输出 3 说明

共有 $5$ 种方法可以使游戏平衡。

• $S = \{\}$，$T = \{\}$。两个牌组的力量均为 $0$。
• $S = \{1, 2\}$，$T = \{\}$。两个牌组的力量均为 $0$。
• $S = \{\}$，$T = \{1, 2\}$。两个牌组的力量均为 $0$。
• $S = \{1\}$，$T = \{2\}$。两个牌组的力量均为 $1$。
• $S = \{2\}$，$T = \{1\}$。两个牌组的力量均为 $1$。

由 ChatGPT 4.1 翻译