#include "inv.h"
#include <algorithm>
typedef long long i64;
const int mod = 998244353;
namespace modulo
{
    int add(int a, int b) { return (a + b >= mod) ? (a + b - mod) : (a + b); }
    int sub(int a, int b) { return (a < b) ? (a - b + mod) : (a - b); }
    int mul(int a, int b) { return 1ll * a * b % mod; }
    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];
    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;
    }
}
void init(int p) { modulo::build(); }
int inv(int x) { return modulo::inv(x); }