CF1513E.Cost Equilibrium

An array is called beautiful if all the elements in the array are equal.

You can transform an array using the following steps any number of times:

1. Choose two indices $i$ and $j$ ($1 \leq i,j \leq n$), and an integer $x$ ($1 \leq x \leq a_i$). Let $i$ be the source index and $j$ be the sink index.
2. Decrease the $i$-th element by $x$, and increase the $j$-th element by $x$. The resulting values at $i$-th and $j$-th index are $a_i-x$ and $a_j+x$ respectively.
3. The cost of this operation is $x \cdot |j-i| $.
4. Now the $i$-th index can no longer be the sink and the $j$-th index can no longer be the source.

The total cost of a transformation is the sum of all the costs in step $3$.

For example, array $[0, 2, 3, 3]$ can be transformed into a beautiful array $[2, 2, 2, 2]$ with total cost $1 \cdot |1-3| + 1 \cdot |1-4| = 5$.

An array is called balanced, if it can be transformed into a beautiful array, and the cost of such transformation is uniquely defined. In other words, the minimum cost of transformation into a beautiful array equals the maximum cost.

You are given an array $a_1, a_2, \ldots, a_n$ of length $n$, consisting of non-negative integers. Your task is to find the number of balanced arrays which are permutations of the given array. Two arrays are considered different, if elements at some position differ. Since the answer can be large, output it modulo $10^9 + 7$.

如果数组中所有元素都相等，则称该数组为优美数组（beautiful array）。

你可以对一个数组执行以下步骤任意多次，从而对其进行变换：

1. 选择两个下标 $i$ 和 $j$（$1 \leq i,j \leq n$），以及一个整数 $x$（$1 \leq x \leq a_i$）。令 $i$ 为源下标（source index），$j$ 为汇下标（sink index）。
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]$ 可以通过代价为 $1 \cdot |1-3| + 1 \cdot |1-4| = 5$ 的变换，变为优美数组 $[2, 2, 2, 2]$。

若一个数组能被变换为优美数组，且该变换的代价唯一确定（即：变换为优美数组的最小代价等于最大代价），则称该数组为平衡数组（balanced array）。

现给定一个长度为 $n$ 的非负整数数组 $a_1, a_2, \ldots, a_n$。你的任务是：求出所有由该数组重排得到的平衡数组的个数。若两个数组在某个位置上的元素不同，则视为不同数组。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）。

Output a single integer — the number of balanced permutations modulo $10^9+7$.

输出一个整数——平衡排列的数量对 $10^9+7$ 取模的结果。

In the first example, $[1, 2, 3]$ is a valid permutation as we can consider the index with value $3$ as the source and index with value $1$ as the sink. Thus, after conversion we get a beautiful array $[2, 2, 2]$, and the total cost would be $2$. We can show that this is the only transformation of this array that leads to a beautiful array. Similarly, we can check for other permutations too.

In the second example, $[0, 0, 4, 4]$ and $[4, 4, 0, 0]$ are balanced permutations.

In the third example, all permutations are balanced.

在第一个例子中，$[1, 2, 3]$ 是一个合法的排列，因为我们可以将值为 $3$ 的位置视为源点（source），将值为 $1$ 的位置视为汇点（sink）。于是，经过转换后我们得到一个优美的数组 $[2, 2, 2]$，总代价为 $2$。可以证明，这是该数组唯一能转化为优美数组的方式。类似地，我们也可以验证其他排列。

在第二个例子中，$[0, 0, 4, 4]$ 和 $[4, 4, 0, 0]$ 是平衡排列。

在第三个例子中，所有排列都是平衡的。