#include "inv.h"
#include <bits/stdc++.h>
using namespace std;

const int B = 1 << 10, B2 = 1 << 20;

int Inv[B2 << 2], mod;
int U[B2], vl[B2];
int* iv;

void init(int P)
{
    iv = Inv + B2;
    iv[1] = 1; mod = P;
    for (int i = 2; i <= (B2 << 1); i++) iv[i] = 1ll * (P - P / i) * iv[P % i] % P;
    for (int i = 1; i <= B2; i++) iv[-i] = iv[i];

    U[0] = 1;
    for (int u = 1; u <= B; u++)
    {
        int uB = u << 10, sum = 0;
        for (int k = 1; k <= B2; k++)
        {
            sum = ((sum += uB) >= P ? sum - P : sum);
            if (sum <= B2)
            {
                if (!U[k]) U[k] = u, vl[k] = sum;
            }
            else if (sum >= P - B2)
            {
                if (!U[k]) U[k] = u, vl[k] = sum - P;
            }
            else
            {
                int nxt = (P - B2 - sum - 1) / uB;
                k += nxt, sum += nxt * uB;
            }
        }
    }
}
int inv(int x) { return 1ll * iv[vl[x >> 10] + (x & 1023) * U[x >> 10]] * U[x >> 10] % mod; }