rt，过不了 $n=10^5$ 的样例，交上去 20pts

调的要崩溃了 求助大佬 qwq

多项式 ln 的版子题是过了的，但也有可能写挂了一些地方 qwq

用了十分丑陋且常数大的封装，请见谅 qwq

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = (1<<19)+5;
const ll Mod = 1ll*479*(1<<21)+1, Rt = 3;
int n, Rev[MAXN];
ll W, w[MAXN];

inline ll Quick_Power(ll x, int p){
	if(!p)	return 1;
	ll tmp = Quick_Power(x, p>>1);
	if(p&1)	return tmp*tmp%Mod*x%Mod;
	else	return tmp*tmp%Mod;
}

inline ll Inv(ll x){
	return Quick_Power(x, Mod-2);
}

struct Polynomial{
	int len;
	ll a[MAXN];
	
	inline void Module(int N){
		for(int i = N; i < len; i++)	a[i] = 0;
		len = N;
		return;
	}
	
	inline void DFT(int N){
		w[0] = 1;
		for(int i = 1; i < N; i++)	w[i] = w[i-1]*W%Mod;
		for(int i = 0; i < N; i++)	if(Rev[i] > i) swap(a[i], a[Rev[i]]);
		for(int i = 2; i <= N; i <<= 1)
			for(int j = 0; j < N; j += i)
				for(int k = 0; k < i/2; k++){
					ll x = a[j+k], y = a[i/2+j+k];
					a[j+k] = (x+y*w[N/i*k]%Mod)%Mod;
					a[i/2+j+k] = (x-y*w[N/i*k]%Mod+Mod)%Mod;
				}
		return;
	}
	
	inline void IDFT(int N){
		W = Inv(W);
		DFT(N);
		ll inv = Inv(N);
		for(int i = 0; i < N; i++)	a[i] = a[i]*inv%Mod;
		return;
	}
	
	Polynomial operator * (const int &tmp)const{
		Polynomial ans; ans.len = len;
		for(int i = 0; i < len; i++)	ans.a[i] = a[i]*tmp%Mod;
		return ans;
	}
	
	Polynomial operator - (const Polynomial &tmp)const{
		Polynomial ans; ans.len = min(len, tmp.len);
		for(int i = 0; i < ans.len; i++)	ans.a[i] = (a[i]-tmp.a[i]+Mod)%Mod;
		return ans;
	}
} f;

inline void Prework(int N){
    W = Quick_Power(Rt, (Mod-1)/N);
	for(int i = N>>1, j = 0; i; i >>= 1){
		int t = j;
		for(int k = 0; k <= t; k++)	Rev[++j] = Rev[k]+i;
	}
	return;
}

Polynomial operator * (const Polynomial &x, const Polynomial &y){
	int N = y.len<<1;//乘法必须算到 N*2 项 
	Prework(N);
	Polynomial X = x, Y = y, ans;
	X.Module(N>>1), Y.Module(N>>1);//对多项式项数取模 
	X.DFT(N), Y.DFT(N);
	for(int i = 0; i < N; i++)	ans.a[i] = X.a[i]*Y.a[i]%Mod;
	ans.IDFT(N);
	ans.Module(N>>1);
	return ans;
}

inline Polynomial Inv_P(Polynomial const &A){
	Polynomial B = (Polynomial){1, {Inv(A.a[0])}};
	for(int N = 2; N <= A.len; N <<= 1){//N 为当前取模的长度 
		B.len = N;
		B = B*2-A*B*B;
	}
	return B;
}

inline Polynomial Direv(Polynomial const &A){
	Polynomial ans;
	for(int i = 1; i < A.len; i++)	ans.a[i-1] = A.a[i]*i%Mod;
	ans.len = A.len;
	return ans;
}

inline Polynomial Inter(Polynomial const A){
	Polynomial ans;
	ans.len = A.len, ans.a[0] = 0;
	for(int i = 1; i < ans.len; i++)	ans.a[i] = A.a[i-1]*Inv(i)%Mod;
	return ans;
}

inline Polynomial Ln(Polynomial const &A){
	return Inter(Direv(A)*Inv_P(A));
}

int main(){
	scanf("%d", &n);
	++n;
	f.len = 1; while(n > f.len) f.len <<= 1;
	f.a[0] = 1;
	ll fac = 1;
	for(int i = 1; i < n; i++){
		fac = fac*i%Mod;
		f.a[i] = Quick_Power(2, 1ll*i*(i-1)/2%(Mod-1))*Inv(fac);
	}
	Polynomial ans = Ln(f);
	cout<<ans.a[n-1]*fac%Mod;
	
	return 0;
}
/*
f(x)：i 个点有标号无向图数量（可不连通）（注意要是 EGF） 
f_i = 2^(i*(i-1)/2)
*/