// #pragma GCC optimize("O3") // #pragma GCC target("popcnt") // #pragma GCC target("avx,avx2,fma") // #pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long const ll INF_MUL=1e13; const ll INF_ADD=1e18; #define pb push_back #define mp make_pair #define nline "\n" #define f first #define s second #define pll pair<ll,ll> #define all(x) x.begin(),x.end() #define vl vector<ll> #define vvl vector<vector<ll>> #define vvvl vector<vector<vector<ll>>> #ifndef ONLINE_JUDGE #define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline; #else #define debug(x); #endif void _print(ll x){cerr<<x;} void _print(char x){cerr<<x;} void _print(string x){cerr<<x;} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";} template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";} template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";} template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";} template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset; //-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- const ll MOD=998244353; const ll MAX=100001; vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1); ll binpow(ll a,ll b,ll MOD){ ll ans=1; a%=MOD; while(b){ if(b&1) ans=(ans*a)%MOD; b/=2; a=(a*a)%MOD; } return ans; } ll inverse(ll a,ll MOD){ return binpow(a,MOD-2,MOD); } void precompute(ll MOD){ for(ll i=2;i<MAX;i++){ fact[i]=(fact[i-1]*i)%MOD; } inv_fact[MAX-1]=inverse(fact[MAX-1],MOD); for(ll i=MAX-2;i>=0;i--){ inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD; } } ll nCr(ll a,ll b,ll MOD){ if((a<0)||(a<b)||(b<0)) return 0; ll denom=(inv_fact[b]*inv_fact[a-b])%MOD; return (denom*fact[a])%MOD; } const ll block_sz=500; ll dp[202][MAX],p; vector<ll> power(MAX,1); ll calc(ll n,ll k){ if(min(n,k)==0){ return 1; } if(n%block_sz){ ll now=((p+1)*calc(n-1,k-1)+nCr(n-1,k,MOD)*power[k])%MOD; return now; } return dp[n/block_sz][k]; } void solve(){ ll m; cin>>m; ll q; cin>>q; p=inverse(m-1,MOD); for(ll i=1;i<MAX;i++){ power[i]=(power[i-1]*p)%MOD; } for(ll i=0;i<MAX;i++){ if(i%block_sz){ continue; } ll cur=i/block_sz; dp[cur][0]=1; for(ll j=1;j<MAX;j++){ dp[cur][j]=(dp[cur][j-1]+nCr(i,j,MOD)*power[j])%MOD; } } while(q--){ ll n,k; cin>>n>>k; ll ans=calc(n-1,k); ll anot=(m*binpow(m-1,n-1,MOD))%MOD; ans=(ans*anot)%MOD; cout<<ans<<nline; } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif ll test_cases=1; //cin>>test_cases; precompute(MOD); while(test_cases--){ solve(); } cout<<fixed<<setprecision(10); cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; }