我计划预习五个小时离散，然后hmc补了这道他自认为非常的裸并且很傻逼自己可以一眼秒的简单题，然后给我讲了讲，然后我失去了一整晚的生命迹象。
首先我们可以发现一个神奇的现象，啊，先排个序，然后我们会发现，一个数 是 合法的(指左边的全部小于等于它，右边的全部大于等于它)，当且仅当它在自己拍完序的位置上。
先不考虑很多相同的。 所以我们可以怎么做呢。从左到右枚举每个 合法的数，然后从左到右 枚举 起点。这样考虑，用dp[n]表示 从 1到 n ，n是合法的数的时候的方案数，ans[n]表示从1到n ， 不合法的方案数。 c[n] 表示从 1 到 n 的 排列总数。 显然 。。。好难描述。
唔，显然我们这样枚举会有很多重复的情况对吧。 艹，我先把hmc讲给我我听懂了的复述一下，一个数是 合法的 方案数， 就是 它左边的数xjb排和右边的数xjb排然后乘起来吧。
好啊其实我觉得他就说了这一局有用的。
所以我们可以采用 总排列数-所有合法情况。然后合法情况会有重复的，这个时候就要进行类似容斥的操作对不对。ex： 1,2 1,2；被计算了两次
所以我们可以 计算出 左边 不合法的 方案数。 用不合法的 再去乘 右边合法的 就一定不会和 之前的重复了，因为之前计算的是左边的合法的。
那么首先我们要知道每个子区间的排列总数，可以边计算顺便枚举，也可以先预处理出来。我比较傻逼混在一起就神志不清了就预处理出来的。
然后我们用 ans[i] 表示 到i 为止 的答案， dp[i]表示到 i为止 合法的 方案数。
第一层枚举 现在的区间 ，[1,i]； 第二层枚举 子区间, j from 1 to i ;
然后维护就好了。
emmm你要是不知道费马小定理的话，，，我也木有办法 也可以用递推式求对不对。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+;
const int N = ;
ll inv[N];
ll n,c[N][N],a[N];
ll qpow(ll a,ll x){
ll res = ;
while (x){
if(x&)
res=res*a%mod;
a=a*a%mod;
x>>=;
}
return res;
}
void init(){
inv[]=;
for(int i=;i<=;i++)
inv[i]=qpow(i,mod-);
}
void slove(int n){
map<int,int> mp;
for(int i=;i<=n;i++){
c[i][i-]=;
mp.clear();
for(int j=i;j<=n;j++){
c[i][j]=c[i][j-]*(j-i+)%mod*inv[++mp[a[j]]]%mod;
}
c[i+][i]=;
}
}
ll dp[N],ans[N];
int main(){
init();
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i];
}
sort(a+,a++n);
slove(n);
ans[]=;
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
dp[i]=(dp[i]+ans[j-]*c[j+][i])%mod;
}
//cout<<dp[i]<<' ';
ans[i]=(c[][i]-dp[i]+mod)%mod;
//cout<<ans[i]<<endl;
}
cout<<ans[n]<<endl;
}