int fac[N],ifac[N];
struct lagrange{
int xs[N],ys[N],w[N],K,p[N],s[N];
inline int fk(int k){
return (k&1)?(-1):(1);
}
void construct(int *f,int siz){
K=siz;
for(int i=1;i<=K;++i){
xs[i]=i;
ys[i]=f[i];
w[i]=(fk(K-i)*ifac[i-1]*ifac[K-i]%mo+mo)%mo;
}
}
int f(int x){
for(int i=1;i<=K;++i){
if(xs[i]==x)return ys[i];
}
int ret=0;
p[0]=s[K+1]=1;
for(int i=1;i<=K;++i){
p[i]=(p[i-1]*((x-xs[i])%mo)%mo+mo)%mo;
}
for(int i=K;i>=1;--i){
s[i]=(s[i+1]*((x-xs[i])%mo)%mo+mo)%mo;
}
for(int i=1;i<=K;++i){
ret=(ret+p[i-1]*s[i+1]%mo*w[i]%mo*ys[i]%mo)%mo;
}
return ret;
}
}La;