rt 样例 2 未过

#include<bits/stdc++.h>
#define int long long
#define mod 1004535809
#define C(x,y) (fac[x]*qpow(fac[y]*fac[x-y]%mod,mod-2)%mod)
//#define C(x,y) (fac[x]*qpow(fac[y],mod-2)%mod*qpow(fac[x-y],mod-2)%mod)
int qpow(int b,int p){
	int ans=1;
//	int qwq=0;
	while(p){
		if(p bitand 1)
			ans=ans*b%mod;
		b=b*b%mod;
		p>>=1;
	}
	return ans;
}

int n;
int fac[1000086];
int f[1000086];
int g[1000086];
signed main(){
	std::cin>>n;
	fac[0]=1;
//	std::cout<<qpow(4,2)<<"\n";
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
//	std::cout<<C(4,2)<<"\n";
	for(int i=1;i<=n;i++)
		g[i]=(1LL<<C(i,2))%mod;
//	for(int i=1;i<=n;i++)
//		std::cout<<g[i]<<" ";
//	puts("");
	for(int i=1;i<=n;i++){
		f[i]=g[i];
		for(int j=1;j<i;j++){
			f[i]=((f[i]-(C(i-1,j-1)*f[j]%mod*g[i-j]%mod))%mod)%mod;
//			std::cout<<i-1<<" "<<j-1<<" "<<C(i-1,j-1)<<"\n";
		}	
	}
	std::cout<<f[n];
	return 0;
}