Sum Nim
NIM is played by two players with several heaps of tokens, on each turn a player can remove any number of tokens (at least one) from one heap. The removed tokens are discarded and play continues. Whoever removes the last token wins.
Gocha qualified for the HackerRank Semi Finals and he wants to learn more about game theory by playing the game of NIM with his best friend Zaza.
They have an array of size to play NIM on. Gocha always makes the first move. Before the game starts Zaza can modify the array to win the game. He can change any two neighboring numbers with their sum, as many times as he wants. (change and with ). He is interested to know how many different arrays he can generate to win the game. (Of course, both of them are playing optimally).
For eaxmple: if Zaza has an array and he has changed the third and fourth elements, the result will be .
Input Format
First line will contain one integer .
Second line will contain the integers of the array .
Constraints
for score
for score
Output Format
Print the answer in a single line.
Sample Input 1
3
1 2 3
Sample Output 1
2
Sample Input 2
4
1 1 1 3
Sample Output 2
3
Sample Input 3
5
2 4 1 2 5
Sample Output 3
11
Explanation
In sample 1, possible variants are: and
In sample 2, possible variants are: , and
Note that he won't generate any array which won't guarantee his win. Thats why (1,1,4) is not an possible variant in sample 2.
xxxxxxxxxx
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada;
procedure Solution is
-- Enter your code here. Read input from STDIN. Print output to STDOUT
end Solution