题目描述

对于一个正整数列$a_1,a_2,...,a_n(n ≥ 3)$ ，如果对于所有 $2 ≤ i ≤ n − 1$，都有$a_{i-1} + a_{i+1} ≥ 2a_i$，则称这个数列是美丽的。 现在有一个正整数列$b_1,...,b_n$，请计算：将$b$数列均匀随机打乱之后，得到的数列是美丽的概率$P$。 你只需要输出 $(P × (n!)) mod 10^9 + 7$即可。

输入格式

第一行一个整数$n$。 接下来一行，共$n$个整数$b_1,b_2,...,b_n$。

输出格式

一个整数，表示答案。

4
1 2 1 3

8

样例输入输出 2

见下发文件。

数据规模

共 10 个测试点。

测试点 1,2 满足$n ≤ 10$。

测试点 3,4 满足$n ≤ 15$。

测试点 5,6 满足$n ≤ 50$。

测试点 7,8 满足$b_i$两两不同。

对于所有数据，满足$3 ≤ n ≤ 100,1 ≤ b_i ≤ 10^9$。

附件

附件下载