結果
| 問題 |
No.3310 mod998
|
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2025-10-24 21:53:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 119 ms / 2,000 ms |
| コード長 | 28,051 bytes |
| コンパイル時間 | 3,938 ms |
| コンパイル使用メモリ | 252,676 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-10-24 21:54:29 |
| 合計ジャッジ時間 | 8,404 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 33 |
ソースコード
#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";
}
}
}