님 게임 3

면접 대비

시간 제한1초메모리 제한512 MB

요약

님 게임에서 각 더미의 돌 개수가 주어질 때, 첫 번째 플레이어가 이기도록 만드는 첫 수의 가짓수를 구한다.

난이도: 보통10점 중 5점
유형: 게임 이론, 비트 연산, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 $k$ 개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.

게임은 구사과가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 구사과가 게임을 이기기 위해서 첫 턴에 할 수 있는 방법의 수를 구하시오.

입력

첫째 줄에 돌 더미의 개수 $N$ ( $1 \le N \le 1000$ )이 주어진다.

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 $P_i$ ( $1 \le P_i \le 1000$ )가 주어진다.

출력

구사과가 게임을 이기기 위해서 첫 턴에 할 수 있는 방법의 수를 출력한다.

예제5

예제 1
입력
```
3
11 15 8
```
예상 출력
```
3
```
예제 2
입력
```
3
11 15 7
```
예상 출력
```
3
```
예제 3
입력
```
3
2 3 4
```
예상 출력
```
1
```
예제 4
입력
```
3
1 2 3
```
예상 출력
```
0
```
예제 5
입력
```
5
99 66 33 98 55
```
예상 출력
```
3
```