32382번 - 돌무더기의 정상화

문제

희원이와 채완이는 바닥에 놓인 돌무더기 $N$개를 보고 재미있는 놀이를 생각해 냈다. $i$번 돌무더기에는 돌이 $A_i$개 쌓여 있다.

먼저 1ドル$부터 $N$까지의 수가 한 번씩 등장하는 길이 $N$의 순열 $T$를 만든다. 그 후 총 $N$턴 동안, 첫 번째 턴부터 $N$번째 턴까지 $i$번째 턴에 다음 규칙에 따라 놀이를 진행한다.

• 희원이가 지금까지 가져간 돌의 개수가 김채완보다 적으면 희원이가 $T_i$번 돌무더기에 있는 모든 돌을 가져간다.
• 그렇지 않으면 채완이가 $T_i$번 돌무더기에 있는 모든 돌을 가져간다.

게임이 끝난 후, 두 사람이 가져간 돌의 개수가 같아지도록 하는 순열 $T$의 개수를 구하여라.

입력

첫째 줄에 돌무더기의 개수 $N$이 주어진다. $(1 \leq N \leq 100)$

둘째 줄에 $i$번 돌무더기에 쌓인 돌의 개수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_{i} \leq 20)$

출력

두 사람이 가져간 돌의 개수를 같게 만드는 순열 $T$의 개수를 1ドル ,円 000 ,円 000 ,円 007$로 나눈 나머지를 출력한다.

제한

힌트