%%%AChen队爷%%%
考察对容斥的基础理解，挺不错的一题
易列答案式
\[\sum_{i=1}^{m+1} P(mex = i) i\]
对这种期望，常使用套路化法
\[\sum_{i=0}^m P(mex>i)\]
和式里面相当于要求已钦定\(i\)个确定的球，求随机选\(n\)次将这\(i\)个球全部染黑的概率。
考虑容斥。先随便选，然后减去一个球未染的，然后加上两个球未染的，...
\[\sum_{i=0}^{m} \sum_{k=0}^{i}C_i^k (\frac{m-k}{m})^n\]
（其实是一个类似二项式反演的容斥）
更换枚举
\[\sum_{k=0}^{m} (\frac{m-k}{m})^n \sum_{i=k}^{m} C_i^k\]
又由组合数的性质
\[\sum_{i=k}^{n} C_i^k = C_{n+1}^{k+1}\]
（容易通过杨辉三角和组合数的递推式证明）
得
\[\sum_{k=0}^{m} (\frac{m-k}{m})^n C_{m+1}^{k+1}\]
直接计算即可。
数据量如果更大的话，可以线筛出所有\(n\)次幂以省掉快速幂的$\log $。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD=1E9+7;
ll QPow(ll x,ll up){
x%=MOD;
ll ans=1;
while(up)
if(up%2==0) x=x*x%MOD,up=up/2;
else ans=ans*x%MOD,up--;
return ans;
}
ll Inv(ll x){
return QPow(x,MOD-2);
}
const ll MXN=1E6+5;
ll fac[MXN],facInv[MXN];
void FacInit(ll n){
fac[0]=1;for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
facInv[n]=Inv(fac[n]);for(ll i=n-1;i>=1;i--) facInv[i]=facInv[i+1]*(i+1)%MOD;
facInv[0]=1;
}
ll C(ll n,ll m){
if(n<m) return 0;
return fac[n]*facInv[m]%MOD*facInv[n-m]%MOD;
}
ll N,M;
int main(){
scanf("%lld%lld",&N,&M);
FacInit(M+1);
ll Ans=0;
for(ll k=0;k<=M;k++){
ll p=1;if(k%2==1) p=(-1+MOD)%MOD;
Ans+=p*QPow(M-k,N)%MOD*C(M+1,k+1)%MOD;
Ans%=MOD;
}
printf("%lld",Ans);
return 0;
}