# RoAlgo Contest #4 (avansati) | slayer2

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 256MB Input: Output:

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$.

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.