Deck-Building Game

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N개의 수가 주어질 때, 각 수를 A 덱, B 덱, 어디에도 넣지 않음 중 하나로 배정하여 두 덱의 XOR 값이 같아지는 경우의 수를 998244353으로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 수학, 비트 연산
정답자: 아직 제출이 없습니다

문제

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

입력

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

The following line consists of $N$ integers $A\_i$ ( $1 ≤ A\_i ≤ 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$ .

예제4

예제 1
입력
```
4
16 12 4 8
```
예상 출력
```
9
```
예제 2
입력
```
4
1 2 4 8
```
예상 출력
```
1
```
예제 3
입력
```
2
1 1
```
예상 출력
```
5
```
예제 4
입력
```
6
1 1 1 2 2 2
```
예상 출력
```
169
```