多项式功底太差。。
对于(F(G(x))=x)有
[[x^n]F(x)=frac{1}{n}[x^{-1}]frac{1}{G^n(x)}
]
[[x^n]H(F(x))=frac{1}{n}[x^{-1}]H'(x)frac{1}{G^n(x)}
]
或者规范一点的写法是([x^n]F(x)=frac{1}{n}[x^{n-1}](frac{x}{G(x)})^n)
对于这题 令([x^i]F(x))为包含(i)个叶子节点的合法树个数
[F(x)=x+sum_{iin D}F^i(x)
]
枚举有几个儿子，(+x)是可以让这个节点成为叶子
[F(x)-sum_{iin D}F^i(x)=x
]
令(G(x)=x-sum_{iin D}x^i) 则
(G(F(x))=x)
代码为了偷懒写一个(O(nlog^2 n))的快速幂。。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=280000,mod=950009857;
int a[MAXN],b[MAXN],tr[MAXN],lim,c[MAXN],G[MAXN],gg[MAXN],n,m;
inline void tmod(int &x){x%=mod;}
inline void rmod(int &x){x+=x>>31&mod;}
inline int qpow(int a,int b){
int res=1;
for(;b;b>>=1,tmod(a*=a))
if(b&1)tmod(res*=a);
return res;
}
inline int ginv(int x){return qpow(x,mod-2);}
inline void ntt(int a[],bool flag){
fp(i,0,lim-1)if(i<tr[i])swap(a[i],a[tr[i]]);
for(int p=2;p<=lim;p<<=1){
const int len=p/2,muli=(1<<18)/p;
fp(j,0,len-1)gg[j]=G[j*muli];
for(int i=0;i<lim;i+=p)
fp(j,i,i+len-1){
const int L=a[j],R=a[j+len]*gg[j-i]%mod;
rmod(a[j]+=R-mod);rmod(a[j+len]=L-R);
}
}
if(!flag)return;const int I=ginv(lim);reverse(a+1,a+lim);
fp(i,0,lim-1)tmod(a[i]*=I);
}
inline void getlim(int n){
for(lim=1;lim<=n;lim<<=1);
fp(i,0,lim-1)tr[i]=(tr[i>>1]>>1)|(i&1?lim>>1:0);
}
void getinv(int deg,int a[],int b[]){
if(deg==1){b[0]=qpow(a[0],mod-2);return;}
getinv((deg+1)/2,a,b);
getlim(deg*2-1);
fp(i,0,deg-1)c[i]=a[i];fp(i,deg,lim-1)c[i]=0;
ntt(c,0);ntt(b,0);
fp(i,0,lim-1)tmod(b[i]=2*b[i]+mod-c[i]*b[i]%mod*b[i]%mod);
ntt(b,1);
fp(i,deg,lim-1)b[i]=0;
}
main(){
G[0]=1;G[1]=qpow(7,(mod-1)/(1<<18));
fp(i,2,MAXN-1)tmod(G[i]=G[i-1]*G[1]);
n=read();m=read();
a[0]=1;fp(i,1,m)a[read()-1]=mod-1;
b[0]=1;getlim(n*2);
for(int k=n;k;k>>=1){
ntt(a,0);
if(k&1){
ntt(b,0);
fp(i,0,lim-1)tmod(b[i]*=a[i]);
ntt(b,1);fp(i,n,lim-1)b[i]=0;
}
fp(i,0,lim-1)tmod(a[i]*=a[i]);
ntt(a,1);fp(i,n,lim-1)a[i]=0;
}
mem(a);getinv(n,b,a);
printf("%lld
",a[n-1]*ginv(n)%mod);
puts("");return 0;
}