【模板】拉格朗日插值法

inline int qpow(int x,int t){
	int ret=1;
	for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
	return ret;
}
struct lagrange{
	int cnt,x[N],y[N],w[N];
	void init(){
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		for(int i=0;i<N;++i){
			w[i]=1;
		}
		cnt=0;
	}
	void insert(int xa,int ya){
		x[++cnt]=xa;
		y[cnt]=ya;
		for(int i=1;i<cnt;++i){
			w[i]=w[i]*qpow(x[i]-xa,mo-2)%mo;
			w[cnt]=w[cnt]*qpow(xa-x[i],mo-2)%mo;
		}
	}
	int calc(int xi){
		for(int i=1;i<=cnt;++i){
			if(xi==x[i])return y[i];
		}
		int ans=0,tmp=1;
		for(int i=1;i<=cnt;++i){
			ans=(ans+w[i]*y[i]%mo*qpow(xi-x[i],mo-2)%mo)%mo;
			tmp=tmp*(xi-x[i])%mo;
		}
		return (ans*tmp%mo+mo)%mo;
	}
};