#include <bits/stdc++.h> using namespace std; /* ------------------------Input Checker---------------------------------- */ long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ if(is_neg){ x= -x; } if(!(l <= x && x <= r)) { cerr << l << ' ' << r << ' ' << x << '\n'; assert(1 == 0); } return x; } else { assert(false); } } } string readString(int l,int r,char endd){ string ret=""; int cnt=0; while(true){ char g=getchar(); assert(g!=-1); if(g==endd){ break; } cnt++; ret+=g; } assert(l<=cnt && cnt<=r); return ret; } long long readIntSp(long long l,long long r){ return readInt(l,r,' '); } long long readIntLn(long long l,long long r){ return readInt(l,r,'\n'); } string readStringLn(int l,int r){ return readString(l,r,'\n'); } string readStringSp(int l,int r){ return readString(l,r,' '); } /* ------------------------Main code starts here---------------------------------- */ const int MAX_T = 1e5; const int MAX_N = 1e5; const int MAX_SUM_LEN = 1e5; #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ff first #define ss second #define mp make_pair #define ll long long #define rep(i,n) for(int i=0;i<n;i++) #define rev(i,n) for(int i=n;i>=0;i--) #define rep_a(i,a,n) for(int i=a;i<n;i++) #define pb push_back ll sum_n = 0, sum_m = 0; int max_n = 0, max_m = 0; int yess = 0; int nos = 0; int total_ops = 0; ll mod = 998244353; using ii = pair<ll,ll>; const ll MX=200000; ll fac[MX], ifac[MX]; ll po(ll x, ll n ){ ll ans=1; while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2; } return ans; } void pre(){ fac[0]=1; rep_a(i,1,MX) fac[i]= (i*fac[i-1])%mod; rep(i,MX) ifac[i]= po(fac[i], mod-2); } ll ncr(ll n, ll r){ if(r>n || r<0 || n<0) return 0; return (fac[n]*((ifac[r]*ifac[n-r])%mod))%mod; } void solve(){ ll m = readIntLn(2,1e3); int q = readIntLn(1,1e5); int sz = 500; int nax = 100005; vector<vector<ll> > dp(nax/sz+5, vector<ll>(nax,0)); ll p = po(m-1,mod-2); ll pw[nax], pm[nax]; pw[0]=pm[0]=1; rep_a(i,1,nax){ pw[i] = (pw[i-1]*p)%mod; pm[i] = (pm[i-1]*(m-1))%mod; } rep(i,1e5+3){ if(i%sz==0){ int ii = i/sz; dp[ii][0]=1; rep_a(j,1,i+1){ dp[ii][j] = (dp[ii][j-1]+ncr(i,j)*pw[j])%mod; } } } int n,k; rep(i,q){ n = readIntSp(2,1e5); k = readIntLn(0,n-1); ll ans = (m*pm[n-1])%mod; ll curr, currn; n--; int t1 = n%sz; if(t1<=k){ curr = dp[n/sz][k-t1]; currn = n-t1+1; k = (k-t1+1); } else{ curr = 1; currn = n-k+1; k = 1; } while(currn<=n){ curr = (1+p)*curr+ncr(currn-1,k)*pw[k]; currn++, k++; curr%=mod; } ans*=curr; ans%=mod; if(ans<0) ans+=mod; cout<<ans<<'\n'; } } signed main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r" , stdin); freopen("output.txt", "w" , stdout); #endif fast; int t = 1; pre(); //t = readIntLn(1,10); for(int i=1;i<=t;i++) { solve(); } assert(getchar() == -1); //assert(sum_n<=3e5); cerr<<"SUCCESS\n"; cerr<<"Tests : " << t << '\n'; cerr<<"Sum of lengths : " << sum_n<<'\n'; //cerr<<"Maximum answer : " << max_n <<'\n'; // // cerr<<"Total operations : " << total_ops << '\n'; // cerr<<"Answered yes : " << yess << '\n'; // cerr<<"Answered no : " << nos << '\n'; cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"; }