Ian managed to find time to play a game with his friend Edi.
They have stones on a table. Stone weighs kilograms. The game is played as follows:
- The two choose a permutation .
- For each , if the stones taken by Ian weigh less than the stones taken by Edi so far, Ian takes the stone with index . Otherwise, Edi takes the stone with index .
Task
Since both are very busy, they ask you to find the number of permutations 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 .
Input data
The first line contains a number representing the number of stones on the table. The next line contains numbers . Stone weighs kilograms.
Output data
The first line will contain a single integer representing the number of permutations with the required property.
Constraints and clarifications
Example 1
stdin
3
1 1 2
stdout
4
Explanation
The permutations are: , , , .
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.