slayer2

Time limit: 1s Memory limit: 256MB Input: Output:

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

They have NN stones on a table. Stone ii weighs aia_i kilograms. The game is played as follows:

  • The two choose a permutation (p1,p2,,pN)(p_1, p_2, \dots, p_N).
  • For each i=1Ni=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 pip_i. Otherwise, Edi takes the stone with index pip_i.

Task

Since both are very busy, they ask you to find the number of permutations pp 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 353998\ 244\ 353.

Input data

The first line contains a number NN representing the number of stones on the table. The next line contains NN numbers a1,a2,,aNa_1, a_2, \dots, a_N. Stone ii weighs aia_i kilograms.

Output data

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

Constraints and clarifications

  • 1N1001 \leq N \leq 100
  • 1ai7001 \leq a_i \leq 700

Example 1

stdin

3
1 1 2

stdout

4

Explanation

The 44 permutations are: (1,3,2)(1, 3, 2), (2,3,1)(2, 3, 1), (3,1,2)(3, 1, 2), (3,2,1)(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.

Log in or sign up to be able to send submissions!