돌무더기의 정상화

시간 제한1초메모리 제한1024 MB

요약

매 턴 뒤처진 사람이 지목된 돌무더기를 가져가는 규칙으로 진행할 때, 두 사람이 같은 수의 돌을 갖게 하는 순열의 개수를 구한다.

문제

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

먼저 $1$ 부터 $N$ 까지의 수가 한 번씩 등장하는 길이 $N$ 의 순열 $T$ 를 만든다. 그 후 총 $N$ 턴 동안, 첫 번째 턴부터 $N$ 번째 턴까지 $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$ 로 나눈 나머지를 출력한다.