CF1906K.Deck-Building Game

You are playing a deck-building game with your friend. There are $N$ cards, numbered from $1$ to $N$. Card $i$ has the value of $A_i$.

You want to build two decks; one for you and one for your friend. A card cannot be inside both decks, and it is allowed to not use all $N$ cards. It is also allowed for a deck to be empty, i.e. does not contain any cards.

The power of a deck is represented as the bitwise XOR of the value of the cards in the deck. The power of an empty deck is $0$.

The game is balanced if both decks have the same power.

Determine the number of ways to build two decks such that the game is balanced. Two ways are considered different if one of the decks contains at least one different card. Since the answer can be very large, calculate the answer modulo $998\,244\,353$.

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

你想构建两副卡组：一副归你，一副归你的朋友。每张卡牌至多只能放入其中一副卡组（即不能同时出现在两副卡组中），且允许不使用全部 $N$ 张卡牌。也允许某副卡组为空（即不包含任何卡牌）。

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

当两副卡组的力量相等时，游戏被视为“平衡”。

请计算构建两副卡组使得游戏平衡的方案数。若两方案中至少有一副卡组所含卡牌不同，则视为不同方案。由于答案可能非常大，请将结果对 $998\,244\,353$ 取模。

The first line consists of an integer $N$ ($2 \le N \le 100\,000$).

The following line consists of $N$ integers $A_i$ ($1 \le A_i \le 100\,000$).

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

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

Output an integer representing the number of ways to build two decks such that the game is balanced. Output the answer modulo $998\,244\,353$.

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

Explanation for the sample input/output #1

Denote $S$ and $T$ as the set of cards in your deck and your friend's deck, respectively. There are $9$ ways to build the decks such that the game is balanced.

• $S = {}$ and $T = {}$. Both decks have the power of $0$.
• $S = {2, 3, 4}$ and $T = {}$. Both decks have the power of $0$.
• $S = {}$ and $T = {2, 3, 4}$. Both decks have the power of $0$.
• $S = {2, 4}$ and $T = {3}$. Both decks have the power of $4$.
• $S = {3}$ and $T = {2, 4}$. Both decks have the power of $4$.
• $S = {2, 3}$ and $T = {4}$. Both decks have the power of $8$.
• $S = {4}$ and $T = {2, 3}$. Both decks have the power of $8$.
• $S = {3, 4}$ and $T = {2}$. Both decks have the power of $12$.
• $S = {2}$ and $T = {3, 4}$. Both decks have the power of $12$.

Explanation for the sample input/output #2

The only way to make the game balanced is to have both decks empty.

Explanation for the sample input/output #3

There are $5$ ways to build the decks such that the game is balanced.

• $S = {}$ and $T = {}$. Both decks have the power of $0$.
• $S = {1, 2}$ and $T = {}$. Both decks have the power of $0$.
• $S = {}$ and $T = {1, 2}$. Both decks have the power of $0$.
• $S = {1}$ and $T = {2}$. Both decks have the power of $1$.
• $S = {2}$ and $T = {1}$. Both decks have the power of $1$.

样例输入/输出 #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$。