传送门
考虑只可能由链或者长度不为3倍数的三的环组成。
然后就把环和链的生成函数列出来生成集合。
多项式$exp$exp即可。
代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int mod=1004535809,N=1e6+5;
typedef long long ll;
typedef vector<int> poly;
inline int add(int a,int b){return (a+=b)>=mod?a-=mod:a;}
inline int dec(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline void Add(int&a,int b){(a+=b)>=mod?a-=mod:a;}
inline void Dec(int&a,int b){a=a<b?a-b+mod:a-b;}
inline void Mul(int&a,int b){a=1ll*a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)Mul(ret,a);return ret;}
namespace Ntt{
	int*w[22];
	int rev[N<<2];
	inline void init(int n){for(ri i=0;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));}
	inline void init_w(){
		for(ri i=1;i<=21;++i)w[i]=new int[1<<(i-1)];
		int w0=ksm(3,(mod-1)>>21);
		w[21][0]=1;
		for(ri i=1,up=1<<20;i<up;++i)w[21][i]=mul(w[21][i-1],w0);
		for(ri i=20;i;--i)for(ri j=0,up=1<<(i-1);j<up;++j)w[i][j]=w[i+1][j<<1]; 
	}
	inline poly operator +(poly a,poly b){
		poly c;int lim=max(a.size(),b.size());c.resize(lim);
		for(int i=0;i<lim;i++) c[i]=add(a[i],i%3?b[i]:0);return c;
	}
	inline void ntt(poly&a,int lim,int type){
		for(ri i=0;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
		for(ri i=1,t=1,a0,a1;i<lim;i<<=1,++t)for(ri j=0,len=i<<1;j<lim;j+=len)
		for(ri k=0;k<i;++k)a0=a[j+k],a1=mul(a[j+k+i],w[t][k]),a[j+k]=add(a0,a1),a[j+k+i]=dec(a0,a1);
		if(~type)return;
		reverse(++a.begin(),a.end());
		for(ri i=0,inv=ksm(lim,mod-2);i<lim;++i)Mul(a[i],inv);
	}
	inline poly operator*(poly a,poly b){
		int m=a.size()+b.size()-1,n=1;
		if(m<=128){
			poly c(m,0);
			int A=a.size(),B=b.size();
			for(ri i=0;i<A;++i)for(ri j=0;j<B;++j)Add(c[i+j],mul(a[i],b[j]));
			return c;
		}
		while(n<m)n<<=1;
		init(n);
		a.resize(n),ntt(a,n,1);
		b.resize(n),ntt(b,n,1);
		for(ri i=0;i<n;++i)Mul(a[i],b[i]);
		return ntt(a,n,-1),a.resize(m),a;
	}
}
using namespace Ntt;
inline poly poly_inv(poly a,int k){
	poly c,b(1,ksm(a[0],mod-2));
	for(ri lim=4,up=k<<2;lim<up;lim<<=1){
		init(lim);
		c=a,c.resize(lim>>1);
		c.resize(lim),ntt(c,lim,1);
		b.resize(lim),ntt(b,lim,1);
		for(ri i=0;i<lim;++i)Mul(b[i],dec(2,mul(b[i],c[i])));
		ntt(b,lim,-1),b.resize(lim>>1);
	}
	return b.resize(k),b;
}
inline poly deriv(poly a){
	for(ri i=0,up=a.size()-1;i<up;++i)a[i]=mul(a[i+1],i+1);
	return a.pop_back(),a;
}
int inv[N<<2];
inline poly integ(poly a){
	a.push_back(0);
	for(ri i=a.size()-1;i;--i)a[i]=mul(a[i-1],inv[i]);
	return a[0]=0,a;
}
inline poly poly_ln(poly a,int k){return a=integ(deriv(a)*poly_inv(a,k)),a.resize(k),a;}
inline poly poly_exp(poly a,int k){
	poly b(1,1),c;
	a.resize(k<<1);
	for(ri lim=2,up=k<<1;lim<up;lim<<=1){
		c=poly_ln(b,lim);
		for(ri i=0;i<lim;++i)c[i]=dec(a[i],c[i]);
		Add(c[0],1);
		b=b*c,b.resize(lim);
	}
	return b.resize(k),b;
}
int fac[N<<1];
poly f;
int n;
int main(){
	freopen("lx.in","r",stdin);
	cin>>n;
	f.resize(n+1);
	init_w();
	inv[1]=1;
	for(ri i=2,up=n<<1;i<=up;++i)inv[i]=mul(inv[mod-mod/i*i],mod-mod/i);
	int mt=1,iv=mod+1>>1;
	f[1]=1;
	for(ri i=2;i<=n;++i)f[i]=add(iv,i>3&&i%3?inv[i*2]:0),Mul(mt,i);
	f=poly_exp(f,n+1);
	cout<<mul(f[n],mt);
}