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

//多倍長整数.
template<const int mod> //mod<2^30.
struct modint{ //mod変更が不可能.
    public:
    long long v;
    static void setmod(int m){} //飾り.
    static constexpr long long getmod(){return mod;}
    modint():v(0){}
    template<typename T>
    modint(T a):v(a){if(v < 0) v += mod;}
    long long val()const{return v;}
 
    modint &operator=(const modint &b) = default;
    modint &operator+()const{return (*this);}
    modint operator-()const{return modint(0)-(*this);}
    modint operator+(const modint b)const{return modint(v)+=b;}
    modint operator-(const modint b)const{return modint(v)-=b;}
    modint operator*(const modint b)const{return modint(v)*=b;}
    modint operator/(const modint b)const{return modint(v)/=b;}
    modint &operator+=(const modint b){
        v += b.v; if(v >= mod) v -= mod;
        return *this;
    }
    modint &operator-=(const modint b){
        v -= b.v; if(v < 0) v += mod; 
        return *this;
    }   
    modint &operator*=(const modint b){v = v*b.v%mod; return *this;}
    modint &operator/=(modint b){ //b!=0 mod素数が必須.
        assert(b.v != 0);
        (*this) *= b.pow(mod-2);
        return *this;
    }
    modint pow(long long n)const{
        modint ret = 1,p = v;
        if(n < 0) p = p.inv(),n = -n;
        while(n){
            if(n&1) ret *= p;
            p *= p; n >>= 1;
        }
        return ret;
    }
    modint inv()const{return pow(mod-2);} //素数mod必須.
 
    modint &operator++(){*this += 1; return *this;}
    modint &operator--(){*this -= 1; return *this;}
    modint operator++(int){modint ret = *this; *this += 1; return ret;}
    modint operator--(int){modint ret = *this; *this -= 1; return ret;}
    friend bool operator==(const modint a,const modint b){return a.v==b.v;}
    friend bool operator!=(const modint a,const modint b){return a.v!=b.v;}
    friend bool operator<(const modint a,const modint b){return a.v<b.v;}
    friend bool operator<=(const modint a,const modint b){return a.v<=b.v;}
    friend bool operator>=(const modint a,const modint b){return a.v>=b.v;}
    friend bool operator>(const modint a,const modint b){return a.v>b.v;}
    friend ostream &operator<<(ostream &os,const modint a){return os<<a.v;}
    friend istream &operator>>(istream &is,modint &a){ //入力はmodをとってくれる.
        long long x; is >> x; x %= mod;
        a = modint(x); return is;
    }
};
using mint = modint<998244353>; const long long mod = 998244353;
namespace to_fold{
__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}
pair<long long,long long> invgcd(long long a,long long b){
    //return {gcd(a,b),x} (xa≡g(mod b))
    a = safemod(a,b);
    if(a == 0) return {b,0};
    long long x = 0,y = 1,memob = b;
    while(a){
        long long q = b/a;
        b -= a*q;
        swap(x,y); y -= q*x;
        swap(a,b);
    }
    if(x < 0) x += memob/b;
    return {b,x};
}
template<long long mod>
long long Garner(const vector<long long> &A,const vector<long long> &M){
    __int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.
    for(int i=1; i<A.size(); i++){
        //assert(gcd(mulM,M.at(i-1)) == 1);
        mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_t
        long long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));
        x += t*mulM;
    }
    return x%mod;
}
int countzero(unsigned long long x){
    if(x == 0) return 64;
    else return __popcount((x&-x)-1);
}
template<typename mint>
struct fftinfo{
    static bool First;
    static mint g,sum_e[30],sum_ie[30]; //sum_e[i]=Π[j=0~i-1]ies[j] * es[i],sum_ie[i]=Π[i=0~j-1]es[j] * ies[i].
    static mint divpow2[30]; //div[i] = 1/(2^i).
    static mint Zeta[30];
    fftinfo(){
        if(!First) return;
        First = false;
        const long long mod = mint::getmod();
        if(mod == 998244353) g = 3;
        else if(mod == 754974721) g = 11;
        else if(mod == 167772161) g = 3;
        else if(mod == 469762049) g = 3;
        else assert(false); //現状RE.
        mint es[30],ies[30]; //es[i]^(2^(2+i))=1.
        int cnt2 = countzero(mod-1);
        mint e = g.pow((mod-1)>>cnt2),ie = e.inv();
        for(int i=cnt2; i>=2; i--){ //e^(2^i)=1;
            es[i-2] = e,e *= e;
            ies[i-2] = ie,ie *= ie;
        }
        mint rot = 1;
        for(int i=0; i<=cnt2-2; i++) sum_e[i] = es[i]*rot,rot *= ies[i];
        rot = 1;
        for(int i=0; i<=cnt2-2; i++) sum_ie[i] = ies[i]*rot,rot *= es[i];
        mint div2n = 1,div2 = mint(1)/2;
        for(int i=0; i<30; i++) divpow2[i] = div2n,div2n *= div2;
        for(int i=0; i<=cnt2; i++) Zeta[i] = g.pow((mod-1)/(2<<i));
    }
};
template<typename mint> bool fftinfo<mint>::First=true;
template<typename mint> mint fftinfo<mint>::g;
template<typename mint> mint fftinfo<mint>::sum_e[30];
template<typename mint> mint fftinfo<mint>::sum_ie[30];
template<typename mint> mint fftinfo<mint>::divpow2[30];
template<typename mint> mint fftinfo<mint>::Zeta[30];
template<typename mint>
void NTT(vector<mint> &A){ //ACLを超参考にしてる.
    int n = A.size();
    assert((n&-n) == n);
    fftinfo<mint> info;
    int h = countzero(n);
    for(int ph=1; ph<=h; ph++){
        int w = 1<<(ph-1),p = 1<<(h-ph);
        mint rot = 1;
        for(int s=0; s<w; s++){
            int offset = s<<(h-ph+1);
            for(int i=0; i<p; i++){
                mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
                A.at(i+offset) = l+r;
                A.at(i+offset+p) = l-r;
            }
            rot *= info.sum_e[countzero(~(unsigned int)(s))];
        }
    }
}
template<typename mint>
void INTT(vector<mint> &A){
    int n = A.size();
    assert((n&-n) == n);
    fftinfo<mint> info;
    const unsigned int mod = mint::getmod();
    int h = countzero(n);
    for(int ph=h; ph>0; ph--){
        int w = 1<<(ph-1),p = 1<<(h-ph);
        mint irot = 1;
        for(int s=0; s<w; s++){
            int offset = s<<(h-ph+1);
            for(int i=0; i<p; i++){
                mint l = A.at(i+offset),r = A.at(i+offset+p);
                A.at(i+offset) = l+r;
                A.at(i+offset+p) = ((unsigned long long)(mod+(unsigned int)l.v-(unsigned int)r.v)*irot.v)%mod;
            }
            irot *= info.sum_ie[countzero(~(unsigned int)(s))];
        }
    }
    mint divn = info.divpow2[h];
    for(auto &a : A) a *= divn;
}
template<typename mint>
vector<mint> convolution(vector<mint> A,vector<mint> B){ //mintじゃないのを突っ込まないように!!!.
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
    if(siza == 0 || sizb == 0) return {};
    if(min(siza,sizb) <= 60){ //naive.
        vector<mint> ret(sizc);
        if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
        else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
        return ret;
    }
    while(N < sizc) N <<= 1;
    A.resize(N),B.resize(N);
    NTT(A); NTT(B);
    for(int i=0; i<N; i++) A.at(i) *= B.at(i);
    INTT(A); A.resize(sizc);
    return A;
}
template<typename T>
vector<long long> convolution_ll(const vector<T> &A,const vector<T> &B){ //long longに収まる範囲.
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
    if(siza == 0 || sizb == 0) return {};
    vector<long long> ret(sizc);
    if(min(siza,sizb) <= 200){ //naive 200はやばい?.
        if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += (long long)A.at(i)*B.at(k);}
        else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += (long long)B.at(i)*A.at(k);}
        return ret;
    }
    const unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
    //const unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;
    const unsigned long long m1m2 = 126663740442542081,m2m3 = 78812994116517889,m3m1 = 354658471880163329,m1m2m3 = 560135205046714369;
    //const unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;
    const unsigned long long i1 = 190329765,i2 = 58587104,i3 = 187290749;
    assert(sizc <= (1<<24));
    using mint1 = modint<mod1>;
    using mint2 = modint<mod2>;
    using mint3 = modint<mod3>;
    vector<mint1> a1(siza),b1(sizb);
    vector<mint2> a2(siza),b2(sizb);
    vector<mint3> a3(siza),b3(sizb);
    for(int i=0; i<siza; i++) a1.at(i) = A.at(i)%mod1;
    for(int i=0; i<sizb; i++) b1.at(i) = B.at(i)%mod1;
    vector<mint1> C1 = convolution(a1,b1);
    for(int i=0; i<siza; i++) a2.at(i) = A.at(i)%mod2;
    for(int i=0; i<sizb; i++) b2.at(i) = B.at(i)%mod2;
    vector<mint2> C2 = convolution(a2,b2);
    for(int i=0; i<siza; i++) a3.at(i) = A.at(i)%mod3;
    for(int i=0; i<sizb; i++) b3.at(i) = B.at(i)%mod3;
    vector<mint3> C3 = convolution(a3,b3);
    vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};
    for(int i=0; i<sizc; i++){
        unsigned long long x = 0;
        x += (C1.at(i).v*i1)%mod1*m2m3;
        x += (C2.at(i).v*i2)%mod2*m3m1;
        x += (C3.at(i).v*i3)%mod3*m1m2;
        long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;
        if(diff < 0) diff += mod1;
        x -= offset.at(diff%5);
        ret.at(i) = x;
    }
    return ret;
}
template<typename mint>
vector<mint> convolution_llmod(const vector<mint> &A,const vector<mint> &B){
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
    if(siza == 0 || sizb == 0) return {};
    vector<mint> ret(sizc);
    if(min(siza,sizb) <= 200){
        for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);
        return ret;
    }
    const long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
    assert(sizc <= (1<<24));
    using mint1 = modint<mod1>;
    using mint2 = modint<mod2>;
    using mint3 = modint<mod3>;
    vector<mint1> a1(siza),b1(sizb);
    vector<mint2> a2(siza),b2(sizb);
    vector<mint3> a3(siza),b3(sizb);
    for(int i=0; i<siza; i++) a1.at(i) = A.at(i).v%mod1;
    for(int i=0; i<sizb; i++) b1.at(i) = B.at(i).v%mod1;
    vector<mint1> C1 = convolution(a1,b1);
    for(int i=0; i<siza; i++) a2.at(i) = A.at(i).v%mod2;
    for(int i=0; i<sizb; i++) b2.at(i) = B.at(i).v%mod2;
    vector<mint2> C2 = convolution(a2,b2);
    for(int i=0; i<siza; i++) a3.at(i) = A.at(i).v%mod3;
    for(int i=0; i<sizb; i++) b3.at(i) = B.at(i).v%mod3;
    vector<mint3> C3 = convolution(a3,b3);
    for(int i=0; i<sizc; i++){
        vector<long long> A = {C1.at(i).v,C2.at(i).v,C3.at(i).v};
        vector<long long> M = {mod1,mod2,mod3};
        ret.at(i) = Garner<mint::getmod()>(A,M);
    }
    return ret;
}
template<typename T>
vector<__int128_t> convolution_i128(const vector<T> &A,const vector<T> &B){ //10^25に収まる範囲.
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
    if(siza == 0 || sizb == 0) return {};
    vector<__int128_t> ret(sizc);
    if(min(siza,sizb) <= 200){ //naive 200はやばい?.
        if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += (long long)A.at(i)*B.at(k);}
        else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += (long long)B.at(i)*A.at(k);}
        return ret;
    }
    const int mod1 = 167772161,mod2 = 469762049,mod3 = 754974721;
    //const int m12 = invgcd(mod1,mod2).second,m13 = invgcd(mod1,mod3).second,m23 = invgcd(mod2,mod3).second,m13m23 = (long long)m13*m23%mod3;
    const int m12 = 104391568,m13 = 323560596,m23 = 399692502,m13m23 = 190329765;
    //const long long w1 = mod1,w2 = w1*mod2;
    const long long w1 = 167772161,w2 = 78812994116517889;
    assert(sizc <= (1<<24));

    using mint1 = modint<mod1>;
    using mint2 = modint<mod2>;
    using mint3 = modint<mod3>;
    vector<mint1> a1(siza),b1(sizb);
    vector<mint2> a2(siza),b2(sizb);
    vector<mint3> a3(siza),b3(sizb);
    for(int i=0; i<siza; i++) a1.at(i) = A.at(i)%mod1;
    for(int i=0; i<sizb; i++) b1.at(i) = B.at(i)%mod1;
    vector<mint1> C1 = convolution(a1,b1);
    for(int i=0; i<siza; i++) a2.at(i) = A.at(i)%mod2;
    for(int i=0; i<sizb; i++) b2.at(i) = B.at(i)%mod2;
    vector<mint2> C2 = convolution(a2,b2);
    for(int i=0; i<siza; i++) a3.at(i) = A.at(i)%mod3;
    for(int i=0; i<sizb; i++) b3.at(i) = B.at(i)%mod3;
    vector<mint3> C3 = convolution(a3,b3);
    for(int i=0; i<sizc; i++){
        long long v2 = C2.at(i).v,v3 = C3.at(i).v;
        long long a = C1.at(i).v;
        long long b = (v2+mod2-a)*m12 %mod2;
        long long c= ((v3+mod3-a)*m13m23+(mod3-b)*m23) %mod3;
        ret.at(i) = a+b*w1+(__int128_t)c*w2;
    }
    return ret;
}
vector<int> convolution_int(const vector<int> &A,const vector<int> &B){ //intに収まる範囲.
    if(A.size() == 0 || B.size() == 0) return {};
    vector<int> ret;
    if(min(A.size(),B.size()) <= 60){
        ret.resize(A.size()+B.size()-1);
        for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
    }
    else{
        using mint1 = modint<998244353>;
        vector<mint1> X(A.size()),Y(B.size()),Z;
        for(int i=0; i<A.size(); i++) X.at(i) = A.at(i);
        for(int i=0; i<B.size(); i++) Y.at(i) = B.at(i);
        Z = convolution(X,Y);
        ret.resize(Z.size());
        for(int i=0; i<Z.size(); i++) ret.at(i) = Z.at(i).v;
    }
    return ret;
}
template<typename mint> 
void NTTdoubling(vector<mint> &A){ //NTTの原理を忘れているため何やってるのか意味が分からない NTT-friendly専用.
        //INTT->resize(2倍）->NTTの代わりにcopy->INTT->謎の操作->NTT->push sizeが小さい時は効率悪いらしいよ.
        int n = A.size();
        fftinfo<mint> info;
        vector<mint> B = A;
        INTT(B);
        mint rot = 1,zeta = info.Zeta[countzero(n)];
        for(auto &v : B) v *= rot,rot *= zeta;
        NTT(B); A.reserve(n<<1);
        for(auto &v : B) A.push_back(v); 
}
bool isNTTfriendly(long long mod){
    if(mod == 998244353 || mod == 754974721 || mod == 16777216 || mod == 469762049) return true;
    return false; //現状false 原子根求める機能を追加してから.
    int have2 = countzero(mod-1);
    return have2 >= 20;//とりあえず2^20でokとする;
}
}
using namespace to_fold;
struct bigint{
    bool isMinus; //0未満か
    vector<int> V; //絶対値の値 5108->{8,0,1,5} 下位ほど前の要素へ入る（9桁ずつ）
    static constexpr int D = 1'000'000'000,log = 9;
 
    bigint():isMinus(false),V(){}
    template<typename T>
    bigint(T a):isMinus(false){
        if(a < 0) isMinus = true,a = -a;
        while(a) V.push_back(a%D),a /= D;
    }
    bigint(bool m,const vector<int> &v):isMinus(m),V(v){}
    bigint(const string &s):isMinus(false){
        assert(s.size());
        if(s.at(0) == '-'){
            isMinus = true;
            for(int i=(int)s.size(); i>0; i-=log){
                int x = 0;
                for(int k=max(1,i-log); k<i; k++) x *= 10,x += s.at(k)-'0';
                V.push_back(x);
            }
        }
        else{
            for(int i=(int)s.size(); i>=0; i-=log){
                int x = 0;
                for(int k=max(0,i-log); k<i; k++) x *= 10,x += s.at(k)-'0';
                V.push_back(x);
            }
        }
        while(V.size() && V.back() == 0) V.pop_back();
    }
    friend istream &operator>>(istream &is,bigint &b){string s; is >> s,b = s; return is;}
    friend ostream &operator<<(ostream &os,const bigint &b){return os<<b.to_string();}
    friend long long get(const bigint &b){ //long longの範囲.
        long long ret = 0;
        for(int i=b.size(); i--;) ret *= D,ret += b.V.at(i);
        return ret;
    }
 
    bigint &operator+(){return *this;}
    bigint operator-()const{
        if(V.size()) return {!isMinus,V};
        return *this;
    }
    bigint &operator++(){*this += 1; return *this;}
    bigint &operator--(){*this -= 1; return *this;}
    bigint operator++(int){bigint ret = (*this); *this += 1; return ret;}
    bigint operator--(int){bigint ret = (*this); *this -= 1; return ret;}
    bigint &operator+=(const bigint &b){return (*this)=(*this)+b;}
    bigint &operator-=(const bigint &b){return (*this)=(*this)-b;}
    bigint &operator*=(const bigint &b){return (*this)=(*this)*b;}
    bigint &operator/=(const bigint &b){return (*this)=(*this)/b;}
    bigint &operator%=(const bigint &b){return (*this)=(*this)%b;}
 
    friend bigint operator+(const bigint &l,const bigint &r){ //l+r O(n).
        if(l.isMinus == r.isMinus) return {l.isMinus,add(l.V,r.V)};
        if(isleEq(l.V,r.V)){  //l<=r abs
            vector<int> v = sub(r.V,l.V);
            bool m = r.isMinus;
            if(iszero(v)) m = false;
            return {m,v};
        }
        else{ //l>r abs
            vector<int> v = sub(l.V,r.V);
            bool m = l.isMinus;
            return {m,v};
        }
    }
    friend bigint operator-(const bigint &l,const bigint &r){ //l-r O(n).
        if(l.isMinus != r.isMinus) return {l.isMinus,add(l.V,r.V)};
        if(isleEq(l.V,r.V)){  //l<=r abs
            vector<int> v = sub(r.V,l.V);
            bool m = r.isMinus^1;
            if(iszero(v)) m = false;
            return {m,v};
        }
        else{ //l>r abs
            vector<int> v = sub(l.V,r.V);
            bool m = l.isMinus;
            return {m,v};
        }
    }
    friend bigint operator*(const bigint &l,const bigint &r){ //l*r O(nlogn or n^2).
        vector<int> v = mul(l.V,r.V);
        bool m = l.isMinus^r.isMinus;
        if(iszero(v)) m = false;
        return {m,v};
    }
    friend bigint operator/(const bigint &l,const bigint &r){return getQR(l,r).first;} //l/r O(nlogn or n^2).
    friend bigint operator%(const bigint &l,const bigint &r){return getQR(l,r).second;} //l%r O(nlogn or n^2).
    friend pair<bigint,bigint> getQR(const bigint &l,const bigint &r){ //{l/r,l%r} O(nlogn or n^2).
        auto qr = div(l.V,r.V);
        bool mq = l.isMinus!=r.isMinus,mr = l.isMinus;
        if(iszero(qr.first)) mq = false;
        if(iszero(qr.second)) mr = false;
        return {{mq,qr.first},{mr,qr.second}};
    }
    friend bool operator==(const bigint &l,const bigint &r){
        if(l.isMinus != r.isMinus || l.size() != r.size()) return false;
        return l.V == r.V;
    }
    friend bool operator!=(const bigint &l,const bigint &r){
        if(l.isMinus != r.isMinus || l.size() != r.size()) return true;
        return l.V != r.V;
    }
    friend bool operator<(const bigint &l,const bigint &r){return isless(l,r);}
    friend bool operator<=(const bigint &l,const bigint &r){return isleEq(l,r);}
    friend bool operator>=(const bigint &l,const bigint &r){return isleEq(r,l);}
    friend bool operator>(const bigint &l,const bigint &r){return isless(r,l);}
 
    bool iszero()const{return !V.size();} //(*this)==0?
    string to_string()const{ //文字列へ.
        if(iszero()) return "0";
        string ret = "";
        if(isMinus) ret += '-';
        for(int i=(int)V.size(); i--;) ret += itos(V.at(i),i+1==V.size());
        return ret;
    }
    long long to_ll()const{ //long longへ.
        long long ret = vtoll(V);
        if(isMinus) ret = -ret;
        return ret;
    }
    __int128_t to_i128()const{ //int128へ.
        __int128_t ret = vtoll(V);
        if(isMinus) ret = -ret;
        return ret;
    }
 
    private:
    unsigned int size()const{return V.size();} //Vのsize(≠桁数)/
    static bool isless(const vector<int> &l,const vector<int> &r){ //配列l<r?
        if(l.size() != r.size()) return l.size()<r.size(); 
        for(int i=(int)l.size(); i--;) if(l.at(i) != r.at(i)) return l.at(i)<r.at(i);
        return false;
    }
    static bool isleEq(const vector<int> &l,const vector<int> &r){ //配列l<=r?
        if(l.size() != r.size()) return l.size()<r.size(); 
        for(int i=(int)l.size(); i--;) if(l.at(i) != r.at(i)) return l.at(i)<r.at(i);
        return true;
    }
    static bool isless(const bigint &l,const bigint &r){ //bigint l<r?
        if(l.isMinus != r.isMinus) return l.isMinus;
        if(l.V == r.V) return false;
        if(isless(l.V,r.V)) return !l.isMinus;
        else return l.isMinus;
    }
     static bool isleEq(const bigint &l,const bigint &r){ //bigint l<=r?
        if(l.isMinus != r.isMinus) return l.isMinus;
        if(l.V == r.V) return true;
        if(isless(l.V,r.V)) return !l.isMinus;
        else return l.isMinus;
    }
    static bool iszero(const vector<int> &v){return !v.size();} // v=0?;
    static bool isone(const vector<int> &v){return v.size()==1&&v.at(0)==1;} //v=1?
    void shrink(){while(V.size() && V.back() == 0) V.pop_back();} //末尾0削除.
    static void shrink(vector<int> &v){while(v.size() && v.back() == 0) v.pop_back();} //与えた配列の末尾0削除.
    
    static vector<int> add(const vector<int> &l,const vector<int> &r){ //l+r
        vector<int> ret(max(l.size(),r.size())+1);
        for(int i=0; i<(int)l.size(); i++) ret.at(i) += l.at(i);
        for(int i=0; i<(int)r.size(); i++) ret.at(i) += r.at(i);
        for(int i=0; i+1<(int)ret.size(); i++) if(ret.at(i) >= D) ret.at(i) -= D,ret.at(i+1)++;
        shrink(ret); return ret;
    }
    static vector<int> sub(const vector<int> &l,const vector<int> &r){ //l-r(>=0)
        assert(isleEq(r,l)); //r<=l必須
        vector<int> ret(l);
        for(int i=0; i<(int)r.size(); i++){
            ret.at(i) -= r.at(i);
            if(ret.at(i) < 0) ret.at(i) += D,ret.at(i+1)--;
        }
        for(int i=(int)r.size(); i<(int)l.size(); i++){
            if(ret.at(i) < 0) ret.at(i) += D,ret.at(i+1)--;
            else break;
        }
        shrink(ret); return ret;
    }
    static vector<int> mul(const vector<int> &l,const vector<int> &r){ //l*r
        if(l.size() == 0 || r.size() == 0) return {};
        auto m = convolution_i128(l,r);
        vector<int> ret; ret.reserve(m.size()+3);
        __int128_t bring = 0;
        for(int i=0; ; i++){
            if(i >= m.size() && bring == 0) break;
            if(i < m.size()) bring += m.at(i);
            ret.push_back(bring%D),bring /= D;
        }
        shrink(ret); return ret;
    }
    static pair<vector<int>,vector<int>> lldivll(const vector<int> &l,const vector<int> &r){ //{l/r,l%r} l,r<10^18
        long long a = vtoll(l),b = vtoll(r);
        return {itov(a/b),itov(a%b)};
    }
    static pair<vector<int>,vector<int>> divint(const vector<int> &l,const vector<int> &r){ //{l/r,l%r} l,r<10^9
        vector<int> qu(l.size());
        long long bring = 0,r1 = r.at(0);
        for(int i=(int)l.size(); i--;){
            bring *= D,bring += l.at(i);
            qu.at(i) = bring/r1,bring %= r1;
        }
        shrink(qu);
        if(bring) return {qu,{(int)bring}};
        return {qu,{}};
    }
    static pair<vector<int>,vector<int>> divnaive(const vector<int> &l,const vector<int> &r){ //{l/r,l%r} l,r<10^9
        int n = l.size(),m = r.size();
        if(max(n,m) <= 2) return lldivll(l,r);
        if(m == 1) return divint(l,r);
        if(isless(l,r)) return {{},l};
        m = D/(r.back()+1); //r.back()を大きくして効率よくするらしいよ.
        vector<int> l2 = mul(l,{m}),r2 = mul(r,{m});
        n = l2.size(),m = r2.size();
        vector<int> qu(n-m+1),re(l2.end()-m,l2.end());
        for(int i=n-m+1; i--;){
            if(re.size() < r2.size()){} //持ち越しが足りない.
            else if(re.size() == r2.size()){
                if(isleEq(r2,re)) qu.at(i) = 1,re = sub(re,r2); //re>r2の場合 r.back()>=D/2よりqu<=1.
            }
            else{
                long long rv = (long long)re.back()*D+re.at(re.size()-2);
                int qv = rv/r2.back(); //これで精度めっちゃいいらしい.
                vector<int> dec = mul(r2,{qv});
                while(isless(re,dec)) qv--,dec = sub(dec,r2); //qvが大きすぎ.
                re = sub(re,dec);
                while(isleEq(r2,re)) qv++,re = sub(re,r2); //qvが小さすぎ.
                qu.at(i) = qv;
            }
            if(i) re.insert(re.begin(),l2.at(i-1)); 
        }
        shrink(qu),shrink(re);
        return {qu,divint(re,{D/(r.back()+1)}).first}; //余りはr.back()を大きくした分割る.
    }
    static vector<int> inv(const vector<int> &v,int deg){ // 1/vのB^-degの絶対誤差.
        int k = deg,n = v.size();
        while(k > 60) k = (k+1)/2;
        vector<int> ret(n+k+1);
        ret.back() = 1;
        ret = divnaive(ret,v).first; //ここで10^-9*kの精度.
        //x<- 2*x - v*x^2で精度を高める.
        while(k < deg){
            vector<int> a = mul(ret,ret); //x^2.
            int d = min(n,2*k+1); //次の精度に合わせた桁数しか要らない.
            vector<int> b(v.end()-d,v.end()),c = mul(a,b); //v*x^2.
            c.erase(c.begin(),c.begin()+d); //cはk+k+1要素以上ある?.
            vector<int> x2(k); x2.reserve(k+k+1);
            for(auto v : add(ret,ret)) x2.push_back(v);
            ret = sub(x2,c),k *= 2;
        }
        ret.erase(ret.begin(),ret.begin()+k-deg);
        return ret;
    }
    static pair<vector<int>,vector<int>> div(const vector<int> &l,const vector<int> &r){ //{l/r,l%r}
        assert(r.size());
        int n = l.size(),m = r.size();
        if(m <= 60 || n-m <= 60) return divnaive(l,r); //60以下で愚直.
        //ニュートン法.
        m = D/(r.back()+1);
        vector<int> l2 = mul(l,{m}),r2 = mul(r,{m});
        n = l2.size(),m = r2.size();
        int deg = n-m+2;
        vector<int> qu = mul(l2,inv(r2,deg));
        qu.erase(qu.begin(),qu.begin()+n+2);
        vector<int> dec = mul(r2,qu);
        while(isless(l2,dec)) qu = sub(qu,{1}),dec = sub(dec,r2); //quが大きい時.
        vector<int> re = sub(l2,dec);
        while(isleEq(r2,re)) qu = add(qu,{1}),re = sub(re,r2); //quが小さい時.
        shrink(qu),shrink(re);
        return {qu,divint(re,{D/(r.back()+1)}).first}; //余りを割るのを忘れずに.
    }
    static string itos(int x,bool leading){ //整数xをstringへ 先頭要素なら0削除.
        assert(0 <= x && x < D);
        string ret = "";
        for(int i=0; i<log; i++) ret += '0'+x%10,x /= 10;
        if(leading){
            while(ret.size() && ret.back() == '0') ret.pop_back();
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
    template<typename T>
    static vector<int> itov(T a){ //整数a(>=0)を配列vへ.
        assert(a >= 0);
        vector<int> ret;
        while(a) ret.push_back(a%D),a /= D;
        return ret;
    }
    static long long vtoll(const vector<int> &v){ //配列vをlong longへ.
        long long ret = 0;
        for(int i=v.size(); i--;) ret *= D,ret += v.at(i);
        return ret;
    }
    static __int128_t vtoi128(const vector<int> &v){ //配列vをint128へ.
        __int128_t ret = 0;
        for(int i=v.size(); i--;) ret *= D,ret += v.at(i);
        return ret;
    }
};



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    using mint = modint<998>; const long long mod = 998;

    int T; cin >> T;
    while(T--){
        int N,M; cin >> N >> M;
        if(N == 0){
            while(M--){
                string s; cin >> s;
                cout << "1\n";
            }
            continue;
        }

        int loop = 1;
        mint sum = N;
        {
            mint v = N*N%mod;
            while(v != N) sum += v,v *= N,loop++;
        }
        while(M--){
            string s; cin >> s;
            bigint v(s);
            auto [p,q] = getQR(v,loop);

            mint answer = 0;
            for(auto c : p.to_string()){
                answer *= 10;
                answer += c-'0';
            }
            answer *= sum;
            int left = q.to_ll();
            mint x = N;
            while(left--){
                answer += x;
                x *= N;
            }
            answer++;
            cout << answer << "\n";
        }
    }
}