#include "inv.h"
typedef unsigned ui;
typedef unsigned long long ull;
const ui mod=1e9+7,M1=1000,M2=M1*M1;
const double invM1=1./M1+1e-15,INV=1.*M2/mod+1e-15;
ui T,len,fra[M2+5],Inv[M2+5],sum[M2+5];
ui q[M2+5];ull p[M2+5];
inline ull abs(const ull&a){
	return a>>63?-a:a;
}
inline void Init(){
	ui i,j,x;
	for(i=1;i^M1;++i){
		const double&INV=1./i+1e-15;
		for(j=0;j^i;++j)if(!sum[x=1ull*j*M2*INV])sum[x]=1,fra[x]=M1*i+j;
	}
	for(i=0;i<=M2;++i){
		if(sum[i])++len,q[len]=fra[i]*invM1,p[len]=1ull*(fra[i]-q[len]*M1)*mod;
		if(i)sum[i]+=sum[i-1];Inv[i]=i>1?1ull*(mod-mod/i)*Inv[mod%i]%mod:i;
	}
}
inline ui Qry(const ui&a){
	static ui q,k;static ull t;
	if(a<=M2)return Inv[a];if(mod-a<=M2)return mod-Inv[mod-a];k=sum[ui(a*INV)];
	if(k<=len){
		q=::q[k];t=1ull*a*q-p[k];
		if(abs(t)<=M2)return 1ull*q*(t>>63?mod-Inv[-t]:Inv[t])%mod;
	}
	if(++k<=len){
		q=::q[k];t=1ull*a*q-p[k];
		if(abs(t)<=M2)return 1ull*q*(t>>63?mod-Inv[-t]:Inv[t])%mod;
	}
	return-1;
}
void init(int p){
	Init();
}
int query(int x){
	return Qry(x);
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:22:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/cc0oLCY3.o: in function `main':
implementer.cpp:(.text.startup+0x1d0): undefined reference to `inv(int)'
collect2: error: ld returned 1 exit status