Normalizing the Stone Piles

Time limit1sMemory limit1024 MB

Summary

Count the permutations of piles for which the greedy rule (the player with fewer stones takes the next pile) leaves both players with equal totals, modulo 1,000,000,007.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Heewon and Chaewan came up with a fun game using $N$ stone piles lying on the floor. Pile $i$ has $A_i$ stones.

First, they make a permutation $T$ of length $N$ in which each number from 1 to $N$ appears exactly once. Then, over $N$ turns in total, they play the game on each turn $i$ , from the first turn to the $N$ -th turn, as follows.

If the number of stones Heewon has taken so far is less than Chaewan's, Heewon takes all stones from pile $T_i$ .
Otherwise, Chaewan takes all stones from pile $T_i$ .

After the game ends, find the number of permutations $T$ that make the number of stones taken by the two players equal.

Input

The first line contains the number of stone piles $N$ . $(1 \leq N \leq 100)$

The second line contains the numbers of stones $A_1, A_2, \cdots, A_N$ in piles $1$ through $N$ , separated by spaces. $(1 \leq A_i \leq 20)$

Output

Print the number of permutations $T$ that make the two players' totals equal, modulo $1\,000\,000\,007$ .

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
4
```
Example 2
Input
```
4
1 2 3 4
```
Expected output
```
8
```