#include<bits/stdc++.h>
//#include"inv.h"
#define ll long long
using namespace std;
const int B=1<<10,B2=1<<21|1;
int P,pool[B2<<1],*iv=pool+B2,val[B2],aBu[B2];//[-2B^2,2B^2]
inline int mul(int x,int y){return (int)(1LL*x*y%P);}
void init(int __P){//P~1e9
	P=__P;
	int lim=P>>10;//P^{\frac{2}{3}}
	for(int u=1;u<=B;u++){//枚举u
		int x=0,uB=u<<10;
		for(int i=0;i<=lim;){
			if(x<=lim) val[i]=u;
			else if(x>=P-lim) val[i]=-u;
			else{
				int t=(P-lim-x-1)/uB;
				x+=t*uB,i+=t;
			}
			x+=uB,i++;
			if(x>=P) x-=P;
		}
	}
	for(int i=0;i<=lim;i++) aBu[i]=mul(i<<10,val[i]+P);
	iv[0]=0,iv[1]=1,iv[-1]=P-1;
	for(int i=2;i<B2;i++) iv[i]=mul(P-P/i,iv[P%i]),iv[-i]=P-iv[i];
}
int inv(int x){//0<=x<P
//	assert(0<=x&&x<P);
	int a=x>>10,b=x&1023,u=val[a];
	return mul(u+P,iv[aBu[a]+b*u]);
}
//int main(){
//	const int P=998244353;
//	init(P);
//	return 0;
//}