//  __  __   _  _____ _   _   _____   ______          __
//  \ \/ /  / \|_   _| | | | |  __ \ / __ \ \   /\   / /
//   \  /  / _ \ | | | | | | | |  | | |  | \ \ /  \ / /
//   /  \ / ___ \| | | |_| | | |__| | |__| |\ V /\ V /
//  /_/\_/_/   \_\_|  \___/  |_____/ \___\_\ \_/  \_/ (TM)

#include <bits/stdc++.h>
#include "inv.h"
using namespace std;
#define ll long long
const int mod=998244353;
struct qhash {
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<int,int,qhash>I;
void init(int p){return;}
int inv(int x)
{
	if(x<=1)return x;
	if(I.find(x)==I.end())I[x]=mod-1LL*mod/x*inv(mod%x)%mod;
	return I[x];
}