RoAlgo Contest #4 (avansati) | slayer2

Ian managed to find time to play a game with his friend Edi.

They have $N$ stones on a table. Stone $i$ weighs $a_i$ kilograms. The game is played as follows:

• The two choose a permutation $(p_1, p_2, \dots, p_N)$.
• For each $i=1 \dots N$, if the stones taken by Ian weigh less than the stones taken by Edi so far, Ian takes the stone with index $p_i$. Otherwise, Edi takes the stone with index $p_i$.

Task

Since both are very busy, they ask you to find the number of permutations $p$ for which at the end of the game the weight of the stones for each player will be the same. Since this number can be very large, display it modulo $998\ 244\ 353$.

Input data

The first line contains a number $N$ representing the number of stones on the table. The next line contains $N$ numbers $a_1, a_2, \dots, a_N$. Stone $i$ weighs $a_i$ kilograms.

Output data

The first line will contain a single integer representing the number of permutations with the required property.

Constraints and clarifications

• $1 \leq N \leq 100$
• $1 \leq a_i \leq 700$

Example 1

stdin

3
1 1 2

stdout

4

Explanation

The $4$ permutations are: $(1, 3, 2)$, $(2, 3, 1)$, $(3, 1, 2)$, $(3, 2, 1)$.

Example 2

stdin

4
1 2 3 8

stdout

0

Explanation

No permutation of stones results in the total weight of stones for each player being the same at the end of the game.