Массив называется красивым, если все его элементы равны.
Вы можете преобразовать некоторый массив, выполнив следующие шаги любое количество раз:
- Выберите два индекса \(i\) и \(j\) (\(1 \leq i,j \leq n\)), а также целое число \(x\) (\(1 \leq x \leq a_i\)). Назовем \(i\) истоком, а \(j\) — стоком.
- Уменьшите \(i\)-й элемент на \(x\), и увеличьте \(j\)-й элемент на \(x\). Итоговые значения на \(i\)-й и \(j\)-й позициях равны \(a_i-x\) и \(a_j+x\) соответственно.
- Стоимость такой операции равна \(x \cdot |j-i| \).
- После этой операции \(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\).
Примечание
В первом примере \([1, 2, 3]\) является сбалансированным массивом, так как мы можем выбрать индекс \(3\) как исток, и индекс \(1\) как сток. После этой операции мы получим красивый массив \([2, 2, 2]\), итоговая стоимость преобразования равна \(2\). Можно показать, что это единственное возможная последовательность операций, приводящая к красивому массиву. Аналогично можно показать, что все другие перестановки тоже сбалансированные.
Во втором примере сбалансированные перестановки — это \([0, 0, 4, 4]\) и \([4, 4, 0, 0]\).
В третьем примере все перестановки являются сбалансированными.