#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

#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;
            }
        }
    }
    inline 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); }