← 返回题目列表

Codeforces · 1513/E

E. 成本均衡

中文机器翻译题面 查看原题

如果数组中的所有元素都相等,则该数组称为美丽数组。

您可以使用以下步骤多次转换数组:

1. Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i,j \leq n$$$), and an integer $$$x$$$ ($$$1 \leq x \leq a_i$$$).令 $$$i$$$ 为源索引,$$$j$$$ 为接收器索引。
2. Decrease the $$$i$$$-th element by $$$x$$$, and increase the $$$j$$$-th element by $$$x$$$.第 $$$i$$$ 和第 $$$j$$$ 索引处的结果值分别为 $$$a_i-x$$$ 和 $$$a_j+x$$$。
3. 此操作的成本为 $$$x \cdot |j-i| $$$。
4. 现在第 $$$i$$$ 个索引不能再作为接收器,并且第 $$$j$$$ 个索引不能再作为源。

例如,数组 $$$[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$$$ 取模。

输入

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

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

输出

输出一个整数 - 以 $$$10^9+7$$$ 为模的平衡排列数。

示例

输入 #1

3
1 2 3

输出 #1

6

输入 #2

4
0 4 0 4

输出 #2

2

输入 #3

5
0 11 12 13 14

输出 #3

120

注意

在第一个示例中,$$$[1, 2, 3]$$$ 是一个有效的排列,因为我们可以将值为 $$$3$$$ 的索引视为源,将值为 $$$1$$$ 的索引视为接收器。因此,转换后我们得到一个漂亮的数组$$$[2, 2, 2]$$$,总成本将是$$$2$$$。我们可以证明,这是该数组唯一能产生漂亮数组的转换。同样,我们也可以检查其他排列。

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

In the third example, all permutations are balanced.