# 拉格朗日反演

$$[x^n]G(x)=\frac{1}{n}[x^{n-1}] (\frac{x}{F(x)})^n$$

$$[x^n]H(G(x))=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{F(x)})^n$$

# 代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q;
}
const int mod=950009857,G=7,N=262150;
int n,m;
int g[N],f[N],rev[N],len[N],inv[N],k1[N],k2[N],k3[N],k4[N],k5[N],k6[N];

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
int re=1;
for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
return re;
}
void getrev(int n)
{for(RI i=0;i<n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len[n]-1));}
void NTT(int *a,int n,int x) {
for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
for(RI i=1;i<n;i<<=1) {
int gn=ksm(G,(mod-1)/(i<<1));
for(RI j=0;j<n;j+=(i<<1)) {
int t1,t2,g=1;
for(RI k=0;k<i;++k,g=1LL*g*gn%mod) {
t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
}
}
}
if(x==1) return;
reverse(a+1,a+n);for(RI i=0;i<n;++i) a[i]=1LL*a[i]*inv[n]%mod;
}
void getinv(int *a,int *b,int n) {
if(n==1) {b[0]=ksm(a[0],mod-2),b[1]=0;return;}
getinv(a,b,n>>1);int kn=n<<1;
for(RI i=0;i<n;++i) k1[i]=a[i],k1[i+n]=b[i+n]=0;
getrev(kn),NTT(k1,kn,1),NTT(b,kn,1);
for(RI i=0;i<kn;++i) b[i]=1LL*(2LL-1LL*b[i]*k1[i]%mod+mod)%mod*b[i]%mod;
NTT(b,kn,-1);
for(RI i=n;i<kn;++i) b[i]=0;
}
void getJF(int *a,int *b,int n)
{for(RI i=1;i<n;++i) b[i]=1LL*a[i-1]*inv[i]%mod; b[0]=0;}
void getdao(int *a,int *b,int n)
{for(RI i=1;i<n;++i) b[i-1]=1LL*a[i]*i%mod; b[n-1]=0;}
void getln(int *a,int *b,int n) {
getdao(a,k3,n),getinv(a,k4,n);
int kn=n<<1;
for(RI i=n;i<kn;++i) k3[i]=k4[i]=0;
getrev(kn),NTT(k3,kn,1),NTT(k4,kn,1);
for(RI i=0;i<kn;++i) k3[i]=1LL*k3[i]*k4[i]%mod;
NTT(k3,kn,-1),getJF(k3,b,n);
for(RI i=n;i<kn;++i) b[i]=0;
}
void getexp(int *a,int *b,int n) {
if(n==1) {b[0]=1,b[1]=0;return;}
getexp(a,b,n>>1);int kn=n<<1;
getln(b,k5,n);
for(RI i=0;i<n;++i) k6[i]=qm(a[i]-k5[i]+mod),k6[i+n]=b[i+n]=0;
k6[0]=qm(k6[0]+1);
getrev(kn),NTT(b,kn,1),NTT(k6,kn,1);
for(RI i=0;i<kn;++i) b[i]=1LL*b[i]*k6[i]%mod;
NTT(b,kn,-1);
for(RI i=n;i<kn;++i) b[i]=0;
}
void getksm(int *a,int *b,int n,int K) {
getln(a,k2,n);
for(RI i=0;i<n;++i) k2[i]=1LL*k2[i]*K%mod;
getexp(k2,b,n);
}
void lagrange_inversion(int kn) {
getinv(g,f,kn);
for(RI i=0;i<kn;++i) f[kn+i]=g[kn+i]=g[i]=0;
getksm(f,g,kn,n);
printf("%lld\n",1LL*g[n-1]*inv[n]%mod);
}

int main()
{
g[0]=qm(g[0]+1);
int kn=1;while(kn<=n) kn<<=1,len[kn]=len[kn>>1]+1;
len[kn<<1]=len[kn]+1,inv[0]=inv[1]=1;
for(RI i=2;i<=(kn<<1);++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
lagrange_inversion(kn);
return 0;
}