N учащихся класса, удобно пронумеровали числами от
1 до
N. На линейке 1 сентября они стояли в ряд, но теперь не уверены в том, в каком порядке они стояли. Однако каждый запомнил следующий факт: абсолютную разницу между количеством учащихся, стоявших слева от этого человека, и количеством учащихся, которые стояли справа от этого человека. Согласно их отчетам, разница для человека
i равна
Ai . На основании этих отчетов, найдите количество возможных расстановок, в которых они стояли. Поскольку ответ может быть очень большим, выведите его по модулю
\(10^9+7\). Обратите внимание, что отчеты могут быть неправильными и, следовательно, не может быть согласованного порядка. В таком случае выведите
0.
Входные данные
В первой строке задается число
N (
\(1<=N<=10^5\)). Во второй строке
N чисел
Ai (
\(0<=A_i<=N-1\)).
Выходные данные
Выведите количество возможных расстановок по модулю
\(10^9+7\).
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
2 4 4 0 2 |
4 |
Возможны 4 расстановки учащихся, а именно:
2 ,1 ,4 ,5 ,3
2 ,5 ,4 ,1 ,3
3 ,1 ,4 ,5 ,2
3 ,5 ,4 ,1 ,2 |
| 2 |
7
6 4 0 2 4 0 2 |
0 |
Любая расстановка не совместима с отчетами. Поэтому ответ 0. |
| 3 |
8
7 5 1 1 7 3 5 3 |
16 |
|