#include "inv.h"
#include <algorithm>
typedef long long i64;
const int mod = 998244353;
namespace modulo
{
    inline int add(int a, int b) { return (a + b >= mod) ? (a + b - mod) : (a + b); }
    inline int sub(int a, int b) { return (a < b) ? (a - b + mod) : (a - b); }
    inline int mul(int a, int b) { return 1ll * a * b % mod; }
    inline int qpow(int x, int p)
    {
        int ans = 1;
        while (p)
        {
            if (p & 1) ans = mul(ans, x);
            x = mul(x, x);
            p >>= 1;
        }
        return ans;
    }
    // n = p^(1/3)
    const int n = 1000, m = n * n, lim = mod / n;
    const int maxn = n + 5, maxm = m + 5, maxl = lim + 5;
    int sum[maxm], frac[maxm], N, F[maxm];
    int cp, p[maxl], I[maxl];
    bool np[maxl];
    inline void build()
    {
        for (int q = 1; q < n; ++q)
            for (int p = 0; p <= q; ++p)
            {
                int i = p * m / q;
                if (!sum[i]) sum[i] = 1, frac[i] = p * n + q;
            }
        for (int i = 1; i <= m; ++i) sum[i] += sum[i - 1];

        for (int i = 0; i <= m; ++i) if (frac[i]) F[N++] = frac[i];
        I[1] = 1;
        for (int i = 2; i <= lim; ++i)
        {
            if (!np[i]) p[cp++] = i, I[i] = qpow(i, mod - 2);
            int k;
            for (int j = 0; j < cp && (k = i * p[j]) <= lim; j++)
            {
                np[k] = 1, I[k] = mul(I[i], I[p[j]]);
                if (i % p[j] == 0)  break;
            }
        }
    }
    int inv(int a)
    {
        int i = 1ll * a * m / mod, k = sum[i];
        i64 f, t;
        int p, q;
        if (k < N)
        {
            f = F[k], p = f / n, q = f - p * n;
            t = 1ll * a * q - 1ll * p * mod;

            if (std::abs(t) <= lim)
                return mul(q, t > 0 ? I[t] : mod - I[-t]);
        }
        if (--k >= 0)
        {
            f = F[k], p = f / n, q = f - p * n;
            t = 1ll * a * q - 1ll * p * mod;
            if (abs(t) <= lim)
                return mul(q, t > 0 ? I[t] : mod - I[-t]);
        }
        return -1;
    }
}
inline void init(int p) { modulo::build(); }
inline int inv(int x) { return modulo::inv(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/ccPcpTjg.o: in function `main':
implementer.cpp:(.text.startup+0x12b): undefined reference to `init(int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x1d0): undefined reference to `inv(int)'
collect2: error: ld returned 1 exit status