熟知指数生成函数（以下简称为EGF）定义为：
并且两个EGF相乘为 (F(x)G(x)) 是数列 (left{sumlimits^n_{k=0}dbinom{n}{k}a^kb^{n-k} ight}_{n=0}^infty) 的EGF
因为我们将 ( ext{e}^x) 再原点处进行泰勒展开得到了数列 ({1,1,cdots}_{n=0}^infty) 的无穷级数形式
所以如果一个数列为 ({1,1,cdots}_{n=0}^infty) 那么它EGF的封闭形式为 ( ext{e}^x)
一个EGF (F(x)=sumlimits_{n=0}^inftydfrac{a_n}{n!}x^n) 同时也是数列 (left{dfrac{a_n}{n!} ight}_{n=0}^infty) 的OGF
我们考虑一个长度为 (n) 数列的排列数（数列中的数互不相同）
显而易见，排列数是 (n!)
写成EGF的形式也就是
那么我们再考虑一个长度为 (n) 的数列的圆排列数
显然对于每个排列，我们将其旋转 (n) 次的到的圆排列相同
显然，圆排列数是 ((n-1)!)
写成EGF的形式：
是不是发现了显然可以 (exp) ？
(exp G(x)=F(x))
在学习群论的时候，我们知道每个置换 (ain S_n) 或是一个循环置换，或是若干个不相交的循环置换的乘积
此时我们把每个排列看成一个置换
长度为 (n) 的排列数方案数即是把其分成 (k) 个集合，然后每个集合的圆排列的方案数的积
熟知 (n) 个点的有标号无向图的个数是 (2^inom{n}{2})
每个无向图可以看作若干个集合构成，每个集合里的元素同属一个连通图
设 (n) 个点的有标号无向图的EGF是 (F(x))，(n) 个点的有标号无向连通图的EGF是 (G(x))
此时我们很容易仿照上文得到 (exp G(x)=F(x))，即 (G(x)=ln F(x))
直接多项式 (ln) 即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 1000001
#define INF 1100000000
#define Kafuu return
#define Chino 0
#define fx(l,n) inline l n
#define set(l,n,ty,len) memset(l,n,sizeof(ty)*len)
#define cpy(f,t,ty,len) memcpy(t,f,sizeof(ty)*len)
#define R register int
#define C const
#define int long long
using namespace std;
C int mod=1004535809,pr=3;
int n,br[N],ppr[N],x=1,invp,invx,A[N],B[N],fc[N];
fx(int,gi)(){
char c=getchar();int s=0,f=1;
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
return s*f;
}
fx(int,pow)(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1) (ans*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return ans;
}
fx(void,NTT)(int *f,C short r,C int x){
R len,hl,exp,uni,s,i;
for(i=0;i<x;i++) br[i]=(br[i>>1]>>1)|((i&1)?x>>1:0);
for(i=0;i<x;i++) if(i<br[i]) swap(f[i],f[br[i]]);
for(len=2,hl=1;len<=x;hl=len,len<<=1){
exp=pow(r==1?pr:invp,(mod-1)/len);
for(i=1;i<hl;i++) ppr[i]=ppr[i-1]*exp%mod;
for(s=0;s<x;s+=len){
for(i=0;i<hl;i++){
uni=ppr[i]*f[i|s|hl]%mod;
f[i|s|hl]=(f[i|s]-uni+mod)%mod;
f[i|s]=(f[i|s]+uni)%mod;
}
}
}
if(r==-1){
invx=pow(x);
for(i=0;i<x;i++) (f[i]*=invx)%=mod;
}
}
fx(void,INV)(int *f,const int x){
static int le[N],ri[N],inv[N];
inv[0]=pow(f[0]);
for(R len=2,hl=1,o;len<=x;hl=len,len<<=1){
for(o=0;o<hl;o++) le[o]=(inv[o]<<1)%mod;
cpy(f,ri,int,len);
NTT(inv,1,len<<1);NTT(ri,1,len<<1);
for(o=0;o<(len<<1);o++) (((inv[o]*=inv[o])%=mod)*=ri[o])%=mod;
NTT(inv,-1,len<<1);
for(o=0;o<len;o++) inv[o]=(le[o]-inv[o]+mod)%mod;
set(inv+len,0,int,len);
}
cpy(inv,f,int,n);
}
fx(void,DER)(int *f,C int len){
for(int i=1;i<len;i++) f[i-1]=f[i]*i%mod;
f[len-1]=0;
}
fx(void,INT)(int *f,C int len){
for(R i=len-1;i>=1;i--) f[i]=f[i-1]*pow(i)%mod;
f[0]=0;
}
signed main(){
ios::sync_with_stdio(0);
n=gi();
n+=1;fc[0]=1;
for(R i=1;i<n;i++) fc[i]=fc[i-1]*i%mod;
for(R i=0;i<n;i++) A[i]=pow(2,i*(i-1)/2)*pow(fc[i])%mod;
cpy(A,B,int,n);
while(x<n) x<<=1;
invp=pow(pr);ppr[0]=1;
INV(A,x);DER(B,n);
while(x<n+n) x<<=1;
NTT(A,1,x);NTT(B,1,x);
for(R i=0;i<x;i++) (A[i]*=B[i])%=mod;
NTT(A,-1,x);INT(A,n);
printf("%lld",A[n-1]*fc[n-1]%mod);
}