#include<bits/stdc++.h>
#include"inv.h"
using namespace std;
#define ll long long
const ll mod = 998244353;
const ll magic = 68996401;
ll magic_inv;
int prime[]={2,3,5,7,11};
ll iv[10000005];
ll qpow(ll a,int w){
    ll ans=1;
    while(w){
        if(w&1)ans=ans*a%mod;
        w>>=1;a=a*a%mod;
    }
    return ans;
}
void init(int p){
    iv[1]=1;
    for(int i=2;i<=10000000;i++)iv[i]=(mod-iv[mod%i]*(mod/i)%mod)%mod;
    magic_inv=qpow(magic,mod-2);
    return ;
}
int inv(int x){
    ll ans=magic_inv;x=x*magic%mod;
    for(int i=0;i<5;i++){
        while(x%prime[i]==0)ans=ans*iv[prime[i]]%mod,x/=prime[i];
    }
    if(x<=10000000)ans=ans*iv[x]%mod;
    else ans=ans*qpow(x,mod-2)%mod;
    return ans;
}