#include "inv.h"

const int mod1 = 1e7;

typedef struct {
	int cnt = 0;
	int head[mod1];
	int nxt[200000007];
	int key[200000007];
	int val[200000007];
	
	inline int find(int cur_key){
		int pos = cur_key % mod1;
		if (head[pos] == 0){
			cnt++;
			head[pos] = cnt;
			key[cnt] = cur_key;
			return cnt;
		}
		int pre = 0, cur = head[pos];
		while (cur != 0 && key[cur] != cur_key){
			pre = cur;
			cur = nxt[cur];
		}
		if (cur == 0){
			nxt[pre] = cur = ++cnt;
			key[cur] = cur_key;
		}
		return cur;
	}
	
	inline void assign(int cur_key, int k){
		val[find(cur_key)] = k;
	}
	
	inline bool count(int cur_key){
		for (register int i = head[cur_key % mod1]; i != 0; i = nxt[i]){
			if (key[i] == cur_key) return true;
		}
		return false;
	}
	
	inline int query(int cur_key){
		for (register int i = head[cur_key % mod1]; i != 0; i = nxt[i]){
			if (key[i] == cur_key) return val[i];
		}
		return 0;
	}
} Hash;

int mod2;
Hash mp;

void init(int p){
	mod2 = p;
}

int inv(int x){
	if (x == 1) return 1;
	if (mp.count(x)) return mp.query(x);
	int ans = mod2 - 1ll * (mod2 / x) * inv(mod2 % x) % mod2;
	mp.assign(x, ans);
	return ans;
}

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);
      |         ~~~~~^~~~~~~~~~
/tmp/ccwYLFiQ.o: in function `init(int)':
answer.code:(.text+0x6): relocation truncated to fit: R_X86_64_PC32 against symbol `mod2' defined in .bss section in /tmp/ccwYLFiQ.o
/tmp/ccwYLFiQ.o: in function `inv(int)':
answer.code:(.text+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `mod2' defined in .bss section in /tmp/ccwYLFiQ.o
answer.code:(.text+0xc9): relocation truncated to fit: R_X86_64_PC32 against symbol `mod2' defined in .bss section in /tmp/ccwYLFiQ.o
collect2: error: ld returned 1 exit status