问了数竞的毛毛搞了一番也没太明白，好在代码蛮好写先记下吧。
#include<bits/stdc++.h>
using namespace std;
const int N=,mod=1e9+;
int n,k,c[N],b[N],a[N],f[N],tmp[N],ans;
inline void qmul(int *x,int *y)
{
for(int i=;i<k*;++i)tmp[i]=;
for(int i=;i<k;++i)
for(int j=;j<k;++j)
tmp[i+j]=(tmp[i+j]+1ll*x[i]*y[j]%mod)%mod;
for(int i=k*-;i>=k;--i)
for(int j=;j<=k;++j)
tmp[i-j]=(tmp[i-j]+1ll*tmp[i]*a[j]%mod)%mod;
for(int i=;i<k;++i)x[i]=tmp[i];
return;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=k;++i)scanf("%d",&a[i]),a[i]=(a[i]%mod+mod)%mod;
for(int i=;i<k;++i)scanf("%d",&f[i]),f[i]=(f[i]%mod+mod)%mod;
c[]=b[]=;
if(n<k){
printf("%d\n",f[n]);
return ;
}
while(n)
{
if(n&)qmul(b,c);
qmul(c,c);n>>=;
}
for(int i=;i<k;++i)ans=(ans+1ll*f[i]*b[i]%mod)%mod;
printf("%d\n",ans);
return ;
}