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.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score