Planeetat

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second
typedef __int128 lll;
 
using namespace std;
typedef complex<ld> co;
const ld PI = atan2((ld)0,(ld)-1);
 
const ll M = 1e9+7;
 
const ll mod1 = 1e6+3;
const ll mod2 = 1e6+33;
const ll mod3 = 1e6+37;
const ll mod4 = 1e6+39;
 
int si;
ll fact[5010];
ll com[5050];
ll dp[5010][5010];
 
 
 
void fft(vector<co>&a, int n, int k) {
	vector<co> ww(n);
	ww[1]=co(1, 0);
	for (int t=0;t<k-1;t++) {
		co c=polar((ld)1, PI/n*(1<<(k-1-t)));
		int p2=(1<<t),p3=p2*2;
		for (int j=p2;j<p3;j++) ww[j*2+1]=(ww[j*2]=ww[j])*c;
	}
	for (int i=0;i<n;i++) {
		int u=0;
		for (int j=1;j<n;j*=2) {u*=2;if (i&j) u++;}
		if (i<u) swap(a[i], a[u]);
	}
	for (int l=1;l<n;l*=2) {
		for (int i=0;i<n;i+=l) {
			for (int it=0,j=i+l,w=l;it<l;it++,i++,j++) {
				co t=a[j]*ww[w++];
				a[j]=a[i]-t;
				a[i]=a[i]+t;
			}
		}
	}
}
vector<ll> conv(const vector<ll>& a, const vector<ll>& b) {
	int as=a.size(), bs=b.size();
	if (as*bs==0) return {};
	int k=0;
	while ((1<<k)<as+bs-1) k++;
	int n=1<<k;
	vector<co> c(n+1);
	for (int i=0;i<n;i++) {
		if (i<as) c[i]=a[i];
		if (i<bs) c[i]={c[i].real(), (ld)b[i]};
	}
	fft(c, n, k);
	c[n]=c[0];
	for (int i=0;i<=n-i;i++) {
		c[i]=conj(c[i]*c[i]-conj(c[n-i]*c[n-i]))*co(0,(ld)1/n/4);
		c[n-i]=conj(c[i]);
	}
	fft(c, n, k);
	vector<ll> r(as+bs-1);
	for (int i=0;i<as+bs-1;i++) r[i]=round(c[i].real());
	return r;
}
 
ll modPow(ll a, ll e, ll mod) {
	ll res=1;
	if (e==-1) return modPow(a,mod-2,mod);
	while (e>0) {
		if (e%2!=0) {
			res*=a;
			res%=mod;
		}
		a*=a;
		a%=mod;
		e/=2;
	}
	return res;
}
 
ll inv(ll a) {
	return modPow(a,M-2,M);
}
 
lll rema(lll a1, lll a2, lll a3, lll a4) {
	lll mmod= ((lll)mod1)*mod2*mod3*mod4;
	lll aa1=a1*(modPow((mod2*mod3*mod4)%mod1,mod1-2,mod1))*mod2*mod3*mod4;
	aa1%=mmod;
	lll aa2=a2*(modPow((mod1*mod3*mod4)%mod2,mod2-2,mod2))*mod1*mod3*mod4;
	aa2%=mmod;
	lll aa3=a3*modPow((mod1*mod2*mod4)%mod3,mod3-2,mod3)*mod1*mod2*mod4;
	aa3%=mmod;
	lll aa4=a4*modPow((mod1*mod2*mod3)%mod4,mod4-2,mod4)*mod1*mod2*mod3;
	aa4%=mmod;
	lll res=(aa1+aa2+aa3+aa4)%mmod;
	return res%M;
}
 
vector<ll> conv2(const vector<ll>& a, const vector<ll> b) {
	int n = a.size();
	if (n==0) return {};
	if (n==1) return {(a[0]*b[0])%M};
	int n1=n/2;
	int n2=n-n1;
	vector<ll> a1(n1);
	vector<ll> a2(n2);
	vector<ll> b1(n1);
	vector<ll> b2(n2);
	vector<ll> a3(n2);
	vector<ll> b3(n2);
	for (int i=0;i<n;i++) {
		if (i<n1) {
			a1[i]=a[i];
			b1[i]=b[i];
		} else {
			a2[i-n1]=a[i];
			a3[i-n1]=a[i];
			b2[i-n1]=b[i];
			b3[i-n1]=b[i];
		}
	}
	for (int i=0;i<n1;i++) {
		a3[i]+=a[i];
		b3[i]+=b[i];
		a3[i]%=M;
		b3[i]%=M;
	}
	vector<ll> c1=conv2(a1,b1);
	vector<ll> c2=conv2(a2,b2);
	vector<ll> c3=conv2(a3,b3);
	for (int i=0;i<2*n1-1;i++) {
		c3[i]-=c1[i];
	}
	for (int i=0;i<2*n2-1;i++) {
		c3[i]-=c2[i];
		while (c3[i]<0) c3[i]+=M;
	}
	vector<ll> c(2*n-1);
	for (int i=0;i<2*n1-1;i++) c[i]+=c1[i];
	for (int i=0;i<2*n2-1;i++) {
		c[i+n1]+=c3[i];
		c[i+n1]%=M;
	}
	for (int i=0;i<2*n2-1;i++) {
		c[i+2*n1]+=c2[i];
		c[i+2*n1]%=M;
	}
	return c;
}
 
void init() {
	fact[0]=1;
	for (int k=1;k<=si;k++) {
		fact[k]=(k*fact[k-1])%M;
		for (int j=1;j<=k;j++) {
			com[k]+=(modPow(k,k-j,M)*inv(fact[k-j]))%M;
			com[k]%=M;
		}
	}
	dp[0][0]=1;
	vector<ll> bb;
	for (int i=0;i<=si;i++) bb.push_back(com[i]);
	for (int j=1;j<=si;j++) {
		vector<ll> aa;
		for (int i=0;i<=si;i++) aa.push_back(dp[j-1][i]);
		vector<ll> cc=conv2(aa,bb);
		for (int i=0;i<=si;i++) dp[j][i]=(cc[i]*inv(i))%M;
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>si;
	init();
	for (int j=1;j<=si;j++) cout<<(dp[j][si]*fact[si])%M<<"\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED