#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair P; typedef pair PP; const ll MOD=1e9+7; //xのy乗 ll mod_pow(ll x,ll y,ll mod){ ll power=x; ll ret = 1; while(y>0){ if(y&1){ ret = ret*power%mod; } power = power*power%mod; y = y>>1; } return ret; } struct combination{ typedef long long ll; std::vector fact,ifact; combination(ll n): fact(n+1),ifact(n+1){ fact[0]=1;//0!=1通り for(ll i=1;i<=n;i++) fact[i] = fact[i-1]*i%MOD; //ifact[n] = fact[n].inv(); // n!の逆元がifact[n] ifact[n] = mod_pow(fact[n],MOD-2,MOD);// n!を(mod-2)乗した後でmodであまりをとった for(ll i=n;i>=1;i--) ifact[i-1] = ifact[i]*i%MOD; } ll operator()(ll n,ll k){ if(k<0 || k>n) return 0; // n!/( k!*(n-k)! ) return (fact[n]*ifact[k])%MOD * ifact[n-k]%MOD; } }; combination comb(1000000); struct Stirling{ vector> S; Stirling(int MAX):S(MAX+1,vector(MAX+1,0)){ for(int k=1;k<=MAX;k++){ S[k][1]=1; } for(int n=2;n<=MAX;n++){ for(int k=2;k<=n;k++){ S[n][k]=S[n-1][k-1] + k*S[n-1][k]%MOD; S[n][k]%=MOD; } } } ll get(ll n,ll k){ if(n<0 || k<0 || n>N; Stirling stir(600); /* kグループに分かれるとする グループ分けのときにばらけない夫婦がn組 ばらける夫婦が N-n組 ばらけない夫婦の通り数が NCn こいつらでkグループを構成するが,kグループの中で空のグループがあってはいけない かつ kグループは区別をつけないで スターリング数S(n,k) ばらける夫婦の通り数.k個のグループあるけど,同じグループになってはいけないのでk*(k-1)通り (k(k-1))^(N-n) */ ll ans=0; for(int k=1;k<=N;k++){ for(int n=0;n<=N;n++){ ll res=comb(N,n); res*=stir.get(n,k); res%=MOD; res*=mod_pow(k*(k-1)%MOD, N-n,MOD); ans+=res; ans%=MOD; } } cout<