题意就是把n个不同的物体放到m个不同的盒子里，斯特林数是求相同的盒子，所以就是求S*(n,m)=m!*S(n,m)
用递推的解法S(n,m)=m*S(n-1,m)+S(n-1,m-1)是O(n^2)肯定会t，所以直接用容斥推的式子。
//#pragma GCC optimize(3,"Ofast","inline") #include<unordered_map> //#include<unordered_set> #include<cstdio> #include<iostream> #include<cmath> #include<functional> #include<cstring> #include<string> #include<cstdlib> #include<queue> #include<map> #include<algorithm> #include<set> #include<stack> #include<vector> #include<sstream> #include<list> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int mod=1000000007; const int N=2e3+10; const int maxn=1e6+7; ll mul[maxn]; ll inv[maxn]; ll c(int n,int m) { return (mul[n]*inv[m])%mod*inv[n-m]%mod; } ll qpow(ll a,ll b,ll p) { ll ans=1%p; a%=p; while(b) { if(b&1)ans=ans*a%p; a=a*a%p; b>>=1; } return ans; } int main() { int n,m; cin>>n>>m; mul[0]=inv[0]=inv[1]=1; for(int i=1;i<=m;i++)mul[i]=mul[i-1]*i%mod; for(int i=2;i<=m;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(int i=1;i<=m;i++)inv[i]=inv[i-1]*inv[i]%mod; ll ans=0; for(int i=0,e=1;i<=m;i++,e*=-1) ans=(ans+c(m,i)*qpow(m-i,n,mod)%mod*e)%mod; cout<<(ans+mod)%mod<<endl; return 0; }