#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll M=998244353;
const int Q=1e3;

pair<int,int> farey[Q*Q+1];
int pre[Q*Q+1],suc[Q*Q+1];
int inv0[M/Q+1];
void build(int a=0,int b=1,int c=1,int d=1){
    int x=a+c,y=b+d;
    if(y>=Q)return;
    build(a,b,x,y);
    farey[x*Q*Q/y]={x,y};
    build(x,y,c,d);
}
void init(int p){
    farey[0]={0,1},farey[Q*Q]={1,1};
    build();
    for(int i=0;i<=Q*Q;i++){
        if(farey[i].second)pre[i]=i;
        else pre[i]=pre[i-1];
    }
    for(int i=Q*Q;i>=0;i--){
        if(farey[i].second)suc[i]=i;
        else suc[i]=suc[i+1];
    }
    inv0[1]=1;
    for(int i=2;i*Q<=M;i++){
        inv0[i]=(ll)(M-M/i)*inv0[M%i]%M;
    }
}

ll inv(int a){
    int p=(ll)a*Q*Q/M,x,y;
    tie(x,y)=farey[pre[p]];
    if (abs((ll)a * y - (ll)M * x) * Q >M)
        tie(x, y) = farey[suc[p]];

    int u = (ll)a * y - (ll)M * x;
    return (ll)(u > 0 ? inv0[u] : M - inv0[-u]) * y % M;
}

// ll qpow(ll a,ll b){
//     ll ans=1;
//     while(b){
//         if(b&1)ans=ans*a%M;
//         b>>=1;
//         a=a*a%M;
//     }
//     return ans;
// }

// mt19937 gen(time(NULL));
// uniform_int_distribution<int> rd(1,M-1);

// void solve(){
//     init();
//     for(int i=0;i<100;i++){
//         int x=rd(gen);
//         cout<<x<<" "<<inv(x)<<" "<<qpow(x,M-2)<<"\n";
//     }
// }

// int main(){
//     ios::sync_with_stdio(0);
//     cin.tie(0);cout.tie(0);
//     int n=1;
//     //cin>>n;
//     while(n--)solve();
//     return 0;
// }