310902: CF1906K. Deck-Building Game

K. Deck-Building Gametime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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$.

Input

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$).

Output

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$.

ExamplesInput

4
16 12 4 8

Output

9

Input

4
1 2 4 8

Output

1

Input

2
1 1

Output

5

Input

6
1 1 1 2 2 2

Output

169

Note

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$.

题目大意：你正在和你的朋友玩一个卡牌构建游戏。有N张卡牌，编号从1到N，每张卡牌有一个值A_i。你需要构建两副牌，一副给你，一副给朋友。一张卡牌不能同时在两副牌中，也可以不用完所有的N张卡牌，一副牌也可以是空的。牌组的“力量”以牌组中卡牌值的按位异或来表示，空牌组的“力量”是0。如果两副牌的力量相同，则游戏是“平衡”的。计算有多少种方式构建两副牌使游戏平衡。如果一副牌至少包含一张不同的卡牌，则认为两种方式是不同的。由于答案可能非常大，计算答案对998,244,353取模。

输入数据格式：第一行包含一个整数N（2 ≤ N ≤ 100,000）。接下来的一行包含N个整数A_i（1 ≤ A_i ≤ 100,000）。

输出数据格式：输出一个整数，表示构建两副平衡牌的方式数，对998,244,353取模。题目大意：你正在和你的朋友玩一个卡牌构建游戏。有N张卡牌，编号从1到N，每张卡牌有一个值A_i。你需要构建两副牌，一副给你，一副给朋友。一张卡牌不能同时在两副牌中，也可以不用完所有的N张卡牌，一副牌也可以是空的。牌组的“力量”以牌组中卡牌值的按位异或来表示，空牌组的“力量”是0。如果两副牌的力量相同，则游戏是“平衡”的。计算有多少种方式构建两副牌使游戏平衡。如果一副牌至少包含一张不同的卡牌，则认为两种方式是不同的。由于答案可能非常大，计算答案对998,244,353取模。 输入数据格式：第一行包含一个整数N（2 ≤ N ≤ 100,000）。接下来的一行包含N个整数A_i（1 ≤ A_i ≤ 100,000）。 输出数据格式：输出一个整数，表示构建两副平衡牌的方式数，对998,244,353取模。