Description

小可可在出题。

小可可非常阴间，她的题目名字都是把 .exe 文件用记事本打开复制几个乱码搞出来的。

这天小可可又要出 \(n\) 道题，且找到了 \(m\) 个不同乱码。小可可非常懒，于是她决定先决定好第一道题目的名字，然后之后每道题目的名字都直接从上一个题目名字中找一个子序列下来当这道题的题目名字。

小可可想知道，在第 \(i\) 道题目题目名字长度为 \(a_i\) \((a_1 ≥ a_2 ≥ ··· ≥ a_n )\) 的情况下，总共会有多少组不同的题目名字呢？

Solution

考虑从 \(a_n\) 倒着做。

那么相当于从第 \(i\) 个字符串加入一些字符来变成第 \(i-1\) 个字符。

有一种避免重复的方法就是在原字符前加入一个不同的字符，最后一个位置没有限制。

然后组合数乱搞就好了。

Code

#include<cstdio>
#include<algorithm>
#define mod 1000000007
#define mx 10000005
#define N 1000005
#define ll long long
using namespace std;
int n;
ll m,ans,sum,a[N],jc[mx],pow1[mx],pow2[mx],ni[mx];
ll ksm(ll x,ll y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
ll C(ll x,ll y) { return jc[x]*ni[y]%mod*ni[x-y]%mod;};
int main()
{
	freopen("qaq.in","r",stdin);
	freopen("qaq.out","w",stdout);
	scanf("%d%lld",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	ni[0]=jc[0]=pow1[0]=pow2[0]=1;
	for (int i=1;i<=mx;++i)
		jc[i]=jc[i-1]*i%mod,pow1[i]=pow1[i-1]*(m-1)%mod,pow2[i]=pow2[i-1]*m%mod;
	ni[(int)1e7]=ksm(jc[(int)1e7],mod-2);
	for (ll i=(int)1e7-1;i;--i)
		ni[i]=ni[i+1]*(i+1)%mod;
	ans=ksm(m,a[1]);
	for (int i=2;i<=n;++i)
	{
		sum=0;
		for (int j=a[i-1];j<=a[i];++j)//有 a[i]-j 个放在末尾
			sum=(sum+C(j-1,a[i-1]-1)*pow1[j-a[i-1]]%mod*pow2[a[i]-j]%mod)%mod;// C(j-1,a[i-1]-1) 是因为保证末尾的是原字符串的字符
		ans=ans*sum%mod;
	}
	printf("%lld",ans);
	return 0;
}