生成函数板子题
无向图是无向联通图的不交并，且带编号，计算时可以直接相乘，那么
[widehat{A} (x) = e^{widehat{B}(x)}
]
[widehat B (x)= ln(widehat A (x)
]
#include <bits/stdc++.h>
using namespace std;
#define rg register
#define gc getchar
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define I inline
const int N = 6e5 + 5, mod = 1004535809;
I int read(){
rg char ch = gc();
rg int f = 0;
rg long long x = 0;
while(!isdigit(ch)) f |= (ch == '-'), ch = gc();
while(isdigit(ch)) x = ((x << 1) + (x << 3) + (ch ^ 48)) % mod, ch = gc();
return f ? mod - x : x;
}
I int ksm(int a, long long b){
int ans = 1;
while(b){ if(b & 1) ans = 1ll * a * ans % mod; b >>= 1; a = 1ll * a * a % mod; }
return ans;
}
int G = 3, Gn = ksm(G, mod - 2);
int f[N], g[N], n, k;
I void fwt_or(int *f, int lim, int flag){
for(int l = 2; l <= lim; l <<= 1)
for(int m = l >> 1, j = 0; j < lim; j += l)
for(int i = j; i < j + m; ++i)
(f[j + m] += flag * f[j]) %= mod;
}
I void fwt_and(int *f, int lim, int flag){
for(int l = 2; l <= lim; l <<= 1)
for(int m = l >> 1, j = 0; j < lim; j += l)
for(int i = j; i < j + m; ++i)
(f[j] += flag * f[j + m]) %= mod;
}
const int inv2 = ksm(2, mod - 2);
I void fwt_xor(int *f, int lim, int flag){
for(int l = 2; l <= lim; l <<= 1)
for(int m = l >> 1, j = 0; j < lim; j += l)
for(int i = j; i < j + m; ++i){
int x = f[i], y = f[i + m];
f[i] = (x + y) % mod; f[i + m] = (x + mod - y) % mod;
if(flag == -1){
f[i] = 1ll * f[i] * inv2 % mod; f[i + m] = 1ll * f[i] * inv2 % mod;
}
}
}
I int get_phi(int x){
int len = sqrt(x);
int res = 1;
rep(i, 2, len){
if(!(x % i)){
x /= i;
res = 1ll * res * (i - 1) % mod;
while(!(x % i)) x /= i, res = 1ll * res * i % mod;
}
}
if(x != 1) res = 1ll * res * (x - 1) % mod;
return res;
}
I int find_root(int x){
int phi = get_phi(x), p = phi;
int len = sqrt(phi);
static int s[N], cnt;
cnt = 0;
rep(i, 2, len){
if(!(p % i)){
p /= i;
s[++cnt] = i;
while(!(p % i)) p /= i;
}
}
if(p != 1) s[++cnt] = p;
rep(i, 1, cnt) cout << s[i] << " "; cout << endl;
cout << phi << endl;
rep(i, 2, mod - 1){
int flag = 0;
rep(j, 1, cnt) if(ksm(i, phi / s[j]) == 1){ flag = 1; break; }
if(!flag) return i;
}
}
int fac[N], ifac[N];
I void get_fac(int n){
fac[0] = ifac[0] = 1;
rep(i, 1, n){
fac[i] = 1ll * fac[i - 1] * i % mod;
ifac[i] = 1ll * ifac[i - 1] * fac[i] % mod;
}
int inv = ksm(ifac[n], mod - 2);
per(i, n, 1){
ifac[i] = 1ll * ifac[i - 1] * inv % mod;
inv = 1ll * fac[i] * inv % mod;
}
}
struct FFT{
int A[N], B[N], c[N], b2[N], bb[N], ib2[N], sa[N], rev[N];
I void NTT(int *a, int lim, int len, int flag){
rep(i, 1, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
rep(i, 1, lim - 1) if(rev[i] > i) swap(a[i], a[rev[i]]);
for(int l = 2; l <= lim; l <<= 1){
const int m = l >> 1, Gi = ksm(flag == 1 ? G : Gn, (mod + 1) / l);
for(int j = 0; j < lim; j += l){
int g = 1;
for(int i = j; i < j + m; ++i, g = 1ll * g * Gi % mod){
int x = a[i], y = 1ll * g * a[i + m] % mod;
a[i] = (x + y) % mod;
a[i + m] = (x + mod - y) % mod;
}
}
}
}
I void mul(int *a, int *b, int na, int nb, int *c){
int lim = 1, len = 0;
while(lim <= na + nb) lim <<= 1, ++len;
memcpy(A, a, (na + 1) * sizeof(int)); memcpy(B, b, (nb + 1) * sizeof(int));
fill(A + na + 1, A + lim, 0); fill(B + nb + 1, B + lim, 0);
NTT(A, lim, len, 1); NTT(B, lim, len, 1);
rep(i, 0, lim - 1) A[i] = 1ll * A[i] * B[i] % mod;
NTT(A, lim, len, -1);
const int inv = ksm(lim, mod - 2);
rep(i, 0, na + nb) c[i] = 1ll * A[i] * inv % mod;
fill(c + na + nb + 1, c + lim, 0);
}
I void ni_ab(int *a, int *b, int n){
int lim = 1;
while(lim <= n) lim <<= 1;
b[0] = ksm(a[0], mod - 2);
for(int xmod = 1, nlen = 2; xmod < lim; xmod <<= 1, ++nlen){
int nlim = xmod << 2;
memcpy(B, b, xmod * sizeof(int)); memcpy(A, a, (xmod << 1) * sizeof(int));
fill(B + xmod, B + nlim, 0); fill(A + (xmod << 1), A + nlim, 0);
NTT(A, nlim, nlen, 1); NTT(B, nlim, nlen, 1);
rep(i, 0, nlim - 1) A[i] = ((B[i] << 1) % mod + mod - 1ll * A[i] * B[i] % mod * B[i] % mod) % mod;
NTT(A, nlim, nlen, -1);
const int inv = ksm(nlim, mod - 2);
rep(i, 0, (xmod << 1) - 1) b[i] = 1ll * A[i] * inv % mod;
}
fill(b + n + 1, b + lim, 0);
}
I void ln(int *a, int *b, int n){//bb b2
int lim = 1, len = 0;
while(lim <= n) lim <<= 1, ++len;
rep(i, 0, n - 1) bb[i] = 1ll * (i + 1) * a[i + 1] % mod;
ni_ab(a, b2, n);
mul(bb, b2, n - 1, n, b);
per(i, n, 1) b[i] = 1ll * b[i - 1] * ksm(i, mod - 2) % mod; b[0] = 0;
}
I void sqrt(int *a, int *b, int n){//bb ib2 b2
int lim = 1, len = 0;
while(lim <= n) lim <<= 1, ++len;
fill(b, b + lim, 0); fill(b2, b2 + lim, 0);
b[0] = 1;
for(int xmod = 1; xmod < lim; xmod <<= 1){
rep(i, 0, xmod - 1) b2[i] = (b[i] << 1) % mod; ni_ab(b2, ib2, (xmod << 1) - 1);
mul(b, b, xmod - 1, xmod - 1, bb);
rep(i, 0, (xmod << 1) - 1) bb[i] = (bb[i] + a[i]) % mod;
mul(bb, ib2, (xmod << 1) - 1, (xmod << 1) - 1, b);
}
}
I void exp(int *a, int *b, int n){//ib2 bb b2 c
int lim = 1; while(lim <= n) lim <<= 1;
fill(b, b + lim, 0);
b[0] = 1;
for(int xmod = 1; xmod < lim; xmod <<= 1){
ln(b, ib2, (xmod << 1) - 1); //ib2 = ln(b);
rep(i, 0, (xmod << 1) - 1) c[i] = (a[i] + mod - ib2[i]) % mod;
c[0] = (c[0] + 1) % mod;
mul(b, c, (xmod << 1) - 1, (xmod << 1) - 1, b);
}
fill(b + n + 1, b + lim, 0);
}
I void pow(int *a, int *b, int n, int _k = k){
int lim = 1; while(lim <= n) lim <<= 1;
ln(a, sa, n);
rep(i, 0, n) sa[i] = 1ll * sa[i] * _k % mod;
exp(sa, b, n);
}
}T;
signed main(){
n = read();
get_fac(n);
f[0] = 1; f[1] = 1;
rep(i, 2, n) f[i] = 1ll * ksm(2, 1ll * i * (i - 1) / 2) * ifac[i] % mod;
T.ln(f, g, n);
printf("%d
", 1ll * g[n] * fac[n] % mod);
return 0;
}