E. Ценовой баланс
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив называется красивым, если все его элементы равны.

Вы можете преобразовать некоторый массив, выполнив следующие шаги любое количество раз:

  1. Выберите два индекса $$$i$$$ и $$$j$$$ ($$$1 \leq i,j \leq n$$$), а также целое число $$$x$$$ ($$$1 \leq x \leq a_i$$$). Назовем $$$i$$$ истоком, а $$$j$$$ — стоком.
  2. Уменьшите $$$i$$$-й элемент на $$$x$$$, и увеличьте $$$j$$$-й элемент на $$$x$$$. Итоговые значения на $$$i$$$-й и $$$j$$$-й позициях равны $$$a_i-x$$$ и $$$a_j+x$$$ соответственно.
  3. Стоимость такой операции равна $$$x \cdot |j-i| $$$.
  4. После этой операции $$$i$$$ больше не может стать стоком, а $$$j$$$ больше не может стать истоком.
Общая стоимость преобразования равна сумме стоимостей на шаге $$$3$$$.

Например, массив $$$[0, 2, 3, 3]$$$ может быть преобразован в красивый массив $$$[2, 2, 2, 2]$$$ с общей стоимостью $$$1 \cdot |1-3| + 1 \cdot |1-4| = 5$$$.

Массив называется сбалансированным, если его можно преобразовать в красивый массив, и стоимость такого преобразования однозначно определена. Другими словами, минимальная стоимость преобразования в красивый массив равна максимальной стоимости.

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$, элементы которого — неотрицательные целые числа. Ваша задача — найти количество сбалансированных массивов, являющихся перестановками данного. Два массива считаются различными, если элементы на некоторых позициях отличаются. Так как ответ может быть большим, выведите его по модулю $$$10^9 + 7$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — размер массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива.

Выходные данные

Выведите одно целое число — количество сбалансированных перестановок по модулю $$$10^9+7$$$.

Примеры
Входные данные
3
1 2 3
Выходные данные
6
Входные данные
4
0 4 0 4
Выходные данные
2
Входные данные
5
0 11 12 13 14
Выходные данные
120
Примечание

В первом примере $$$[1, 2, 3]$$$ является сбалансированным массивом, так как мы можем выбрать индекс $$$3$$$ как исток, и индекс $$$1$$$ как сток. После этой операции мы получим красивый массив $$$[2, 2, 2]$$$, итоговая стоимость преобразования равна $$$2$$$. Можно показать, что это единственное возможная последовательность операций, приводящая к красивому массиву. Аналогично можно показать, что все другие перестановки тоже сбалансированные.

Во втором примере сбалансированные перестановки — это $$$[0, 0, 4, 4]$$$ и $$$[4, 4, 0, 0]$$$.

В третьем примере все перестановки являются сбалансированными.