Mode: On-Campus Exam Pattern: 3 DSA qs in 90 mins OA Date: 2026-10-25

Two players, Player 1 and Player 2, play a game using N trays, where the i-th tray contains A[i] candies.

The rules of the game are as follows:

1. Player 1 always makes the first move.
2. On each turn, a player must choose a tray containing candies and remove any positive, even number of candies from it.
3. If a tray becomes empty after a move, it is removed from the game.
4. Both players play optimally.
5. A player who cannot make a valid move loses the game.
6. Before the game begins, Player 2 can rearrange the trays in any order.

Determine the number of distinct arrangements of the trays for which Player 1 wins, assuming both players play optimally.

For this version, assume that arrangements are considered distinct by position, even when some trays contain the same number of candies, and that every tray contains a positive integer number of candies.

Input Format

• The first line contains an integer N, representing the number of trays.
• The second line contains N space-separated integers A[1], A[2], ..., A[N], representing the number of candies in each tray.

Output Format

Print a single integer representing the number of arrangements that allow Player 1 to win.

Example 1

Input

3
1 2 3

Output

6

Explanation

There are 3 trays, containing 1, 2, and 3 candies. Under the assumed rules, the order of the trays does not affect the possible moves or the outcome of the game. Therefore, either all six positional arrangements allow Player 1 to win, or none do.

For this illustrative example, assume Player 1 wins for this set of tray sizes. Since all three tray sizes are distinct, there are 3! = 6 distinct arrangements, so the answer is 6.

Constraints

• 1 ≤ N ≤ 10^5
• 1 ≤ A[i] ≤ 10^9