#ifndef INCLUDE_MODE #define INCLUDE_MODE /* #define SUBMIT_ONLY */ #define DEBUG_OUTPUT #define SAMPLE_CHECK C #endif #ifdef INCLUDE_MAIN VO Solve() { CIN( string , S , T ); int size = max( S.size() , T.size() ); S.resize( size , 'a' ); T.resize( size , 'a' ); CEXPR( char , w , 26 ); string diff_prep( size , 'a' ); FOR( i , 0 , size ){ diff_prep[i] = 'a' + ( S[i] + w - T[i] ) % w; } using MOD = Mod; AdditiveMonoid magma{}; ShiftableRollingHash srh{}; ShiftableRollingHashBiModule bimodule{ srh }; LazySqrtDecomposition diff{ magma , bimodule , srh.PointwiseEncode( diff_prep ) }; string a = "a"; using Code = decltype( srh.Encode( a ) ); auto r_inv = get<0>( srh.Encode( a ) ) / ( srh.r() - 1 ); auto CheckDifferent = [&]( const Code& v , const int& ){ auto& [hash,power,length] = v; return hash != ( power - 1 ) * r_inv; }; IntervalAddBIT s_act( size ); IntervalAddBIT t_act( size ); CIN( int , Q ); FOR( q , 0 , Q ){ CIN( int , type ); if( type == 1 ){ CIN( int , l , r , x ); --l; --r; diff.IntervalAct( l , r , x ); s_act.IntervalAdd( l , r , x ); } else if( type == 2 ){ CIN( int , l , r , x ); --l; --r; diff.IntervalAct( l , r , -x ); t_act.IntervalAdd( l , r , x ); } else if( type == 3 ){ CIN( int , p ); --p; int x = diff.Search( p , CheckDifferent ); if( x == -1 ){ COUT( "Equals" ); } else { MOD s_x = ( s_act[x] + ( S[x] - 'a' ) ) % w; MOD t_x = ( t_act[x] + ( T[x] - 'a' ) ) % w; assert( s_x != t_x ); COUT( s_x > t_x ? "Greater" : "Lesser" ); } } } } REPEAT_MAIN(1); #else /* INCLUDE_MAIN */ #ifdef INCLUDE_SUB /* 圧縮時は中身だけ削除する。*/ IN VO Experiment() { } /* 圧縮時は中身だけ削除する。*/ IN VO SmallTest() { } /* 圧縮時は中身だけ削除する。*/ IN VO RandomTest( const int& test_case_num ) { REPEAT( test_case_num ){ } } #define INCLUDE_MAIN #include __FILE__ #else /* INCLUDE_SUB */ #ifdef INCLUDE_LIBRARY /* VVV 常設でないライブラリは以下に挿入する。*/ #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Mathematics/SetTheory/DirectProduct/AffineSpace/BIT/IntervalAdd/Debug/a_Body.hpp" #else #define SFINAE_FOR_BIT_BS enable_if_t>* TE CL AbstractBIT{PU:ABELIAN_GROUP m_M;int m_SZ;VE m_fenwick;int m_PW;IN AbstractBIT(ABELIAN_GROUP M,CRI SZ = 0);IN AbstractBIT(ABELIAN_GROUP M,CO VE& a);TE IN VO Initialise(CO Args&... args);IN VO Set(CRI i,CO U& u);VO Add(CRI i,CO U& u);IN CRI SZ()CO NE;IN U OP[](CRI i);IN U Get(CRI i);IN CO U& LSBSegmentSum(CRI j)CO;U InitialSegmentSum(CRI i_final);IN U IntervalSum(CRI i_start,CRI i_final);TE int Search(CO F& f);TE IN int Search(CRI i_start,CO F& f);IN int Search(CO U& u);IN int Search(CRI i_start,CO U& u);IN VO COruct();};TE AbstractBIT(ABELIAN_GROUP M,CO Args&... args)-> AbstractBIT,ABELIAN_GROUP>;TE CL BIT:PU AbstractBIT>{PU:TE IN BIT(CO Args&... args);};TE BIT(CO VE& a)-> BIT; TE IN AbstractBIT::AbstractBIT(ABELIAN_GROUP M,CRI SZ):m_M(MO(M)),m_SZ(SZ),m_fenwick(m_SZ + 1,m_M.Zero()),m_PW(1){COruct();}TE IN AbstractBIT::AbstractBIT(ABELIAN_GROUP M,CO VE& a):m_M(MO(M)),m_SZ(a.SZ()),m_fenwick(m_SZ + 1,m_M.Zero()),m_PW(1){COruct();for(int j = 1;j <= m_SZ;j++){U& fenwick_j = m_fenwick[j];int i = j - 1;fenwick_j = a[i];int i_lim = j -(j & -j);WH(i > i_lim){fenwick_j = m_M.Sum(MO(fenwick_j),m_fenwick[i]);i -=(i & -i);}}}TE IN VO AbstractBIT::COruct(){ST_AS(is_same_v>);WH(m_PW < m_SZ){m_PW <<= 1;}}TE TE IN BIT::BIT(CO Args&... args):AbstractBIT>(AdditiveGroup(),args...){}TE TE IN VO AbstractBIT::Initialise(CO Args&... args){AbstractBIT temp{m_M,args...};m_SZ = temp.m_SZ;m_fenwick = MO(temp.m_fenwick);m_PW = temp.m_PW;}TE IN VO AbstractBIT::Set(CRI i,CO U& u){Add(i,m_M.Sum(m_M.Inverse(IntervalSum(i,i)),u));}TE VO AbstractBIT::Add(CRI i,CO U& u){int j = i + 1;WH(j <= m_SZ){U& fenwick_j = m_fenwick[j];fenwick_j = m_M.Sum(MO(fenwick_j),u);j +=(j & -j);}RE;}TE IN CRI AbstractBIT::SZ()CO NE{RE m_SZ;}TE IN U AbstractBIT::OP[](CRI i){AS(0 <= i && i < m_SZ);RE IntervalSum(i,i);}TE IN U AbstractBIT::Get(CRI i){RE OP[](i);}TE IN CO U& AbstractBIT::LSBSegmentSum(CRI j)CO{AS(0 < j && j <= m_SZ);RE m_fenwick[j];}TE U AbstractBIT::InitialSegmentSum(CRI i_final){U sum = m_M.Zero();int j = min(i_final + 1,m_SZ);WH(j > 0){sum = m_M.Sum(MO(sum),m_fenwick[j]);j -= j & -j;}RE sum;}TE IN U AbstractBIT::IntervalSum(CRI i_start,CRI i_final){RE m_M.Sum(m_M.Inverse(InitialSegmentSum(i_start - 1)),InitialSegmentSum(i_final));}TE TE int AbstractBIT::Search(CO F& f){int j = 0;int PW = m_PW;U sum = m_M.Zero();U sum_next = sum;WH(PW > 0){int j_next = j | PW;if(j_next <= m_SZ){sum_next = m_M.Sum(MO(sum_next),m_fenwick[j_next]);if(f(sum_next,j_next - 1)){sum_next = sum;}else{sum = sum_next;j = j_next;}}PW >>= 1;}RE j;}TE TE IN int AbstractBIT::Search(CRI i_start,CO F& f){CO U u_inv = m_M.Inverse(InitialSegmentSum(i_start - 1));RE max(i_start,Search([&](CO U& sum,CRI i){RE i_start <= i && f(m_M.Sum(u_inv,sum),i);}));}TE IN int AbstractBIT::Search(CO U& u){RE Search([&](CO U& sum,CRI){RE !(sum < u);});}TE IN int AbstractBIT::Search(CRI i_start,CO U& u){RE max(i_start,Search(m_M.Sum(InitialSegmentSum(i_start - 1),u)));}TE IN OS& OP<<(OS& os,AbstractBIT& bit){auto&& SZ = bit.SZ();for(int i = 0;i < SZ;i++){(i == 0?os:os << " ")<< bit[i];}RE os;} TE CL AbstractIntervalAddBIT{PU:Z_MODULE m_M;AbstractBIT m_bit_0;AbstractBIT m_bit_1;AbstractIntervalAddBIT(Z_MODULE M,CRI SZ = 0);AbstractIntervalAddBIT(Z_MODULE M,CO VE& a);TE IN VO Initialise(CO Args&... args);IN VO Set(CRI i,CO U& u);IN VO Add(CRI i,CO U& u);IN VO IntervalAdd(CRI i_start,CRI i_final,CO U& u);IN CRI SZ()CO NE;IN U OP[](CRI i);IN U Get(CRI i);IN U InitialSegmentSum(CRI i_final);IN U IntervalSum(CRI i_start,CRI i_final);TE int Search(CO F& f);TE IN int Search(CRI i_start,CO F& f);IN int Search(CO U& u);IN int Search(CRI i_start,CO U& u);};TE AbstractIntervalAddBIT(Z_MODULE M)-> AbstractIntervalAddBIT,Z_MODULE>;TE CL IntervalAddBIT:PU AbstractIntervalAddBIT>{PU:TE IN IntervalAddBIT(CO Args&... args);};TE IntervalAddBIT(CO VE& a)-> IntervalAddBIT; TE AbstractIntervalAddBIT::AbstractIntervalAddBIT(Z_MODULE M,CRI SZ):m_M(MO(M)),m_bit_0(m_M,SZ),m_bit_1(m_M,SZ){}TE AbstractIntervalAddBIT::AbstractIntervalAddBIT(Z_MODULE M,CO VE& a):m_M(MO(M)),m_bit_0(m_M),m_bit_1(m_M){CO int SZ = a.SZ();VE diff(SZ,m_M.Zero());diff[0]= a[0];for(int i = 1;i < SZ;i++){diff[i]= m_M.Sum(m_M.Inverse(a[i-1]),a[i]);}m_bit_1.Initialise(diff);for(int i = 1;i < SZ;i++){U& diff_i = diff[i];diff_i = m_M.ScalarProduct(1 - i,MO(diff_i));}m_bit_0.Initialise(diff);}TE TE IN IntervalAddBIT::IntervalAddBIT(CO Args&... args):AbstractIntervalAddBIT>(Module(),args...){}TE TE IN VO AbstractIntervalAddBIT::Initialise(CO Args&... args){AbstractIntervalAddBIT temp{m_M,args...};m_bit_0 = MO(temp.m_bit_0);m_bit_1 = MO(temp.m_bit_1);}TE IN VO AbstractIntervalAddBIT::Set(CRI i,CO U& u){Add(i,m_M.Sum(m_M.Inverse(IntervalSum(i,i)),u));}TE IN VO AbstractIntervalAddBIT::Add(CRI i,CO U& u){AS(0 <= i && i < SZ());IntervalAdd(i,i,u);}TE IN VO AbstractIntervalAddBIT::IntervalAdd(CRI i_start,CRI i_final,CO U& u){CO U u_inv = m_M.Inverse(u);m_bit_0.Add(i_start,m_M.ScalarProduct((i_start - 1),u_inv));m_bit_0.Add(i_final + 1,m_M.ScalarProduct(i_final,u));m_bit_1.Add(i_start,u);m_bit_1.Add(i_final + 1,u_inv);}TE IN CRI AbstractIntervalAddBIT::SZ()CO NE{RE m_bit_0.SZ();}TE IN U AbstractIntervalAddBIT::OP[](CRI i){AS(0 <= i && i < SZ());RE IntervalSum(i,i);}TE IN U AbstractIntervalAddBIT::Get(CRI i){RE OP[](i);}TE IN U AbstractIntervalAddBIT::InitialSegmentSum(CRI i_final){RE m_M.Sum(m_bit_0.InitialSegmentSum(i_final),m_M.ScalarProduct(i_final,m_bit_1.InitialSegmentSum(i_final)));}TE TE int AbstractIntervalAddBIT::Search(CO F& f){int l = -1,r = SZ();WH(l + 1 < r){CO int m =(l + r)>> 1;(f(InitialSegmentSum(m),m)?r:l)= m;}RE r;}TE TE IN int AbstractIntervalAddBIT::Search(CRI i_start,CO F& f){CO U u_inv = m_M.Inverse(InitialSegmentSum(i_start - 1));RE max(i_start,Search([&](CO U& sum,CRI i){RE i_start <= i && f(m_M.Sum(u_inv,sum),i);}));}TE IN int AbstractIntervalAddBIT::Search(CO U& u){RE Search([&](CO U& sum,CRI){RE !(sum < u);});}TE IN int AbstractIntervalAddBIT::Search(CRI i_start,CO U& u){RE max(i_start,Search(m_M.Sum(InitialSegmentSum(i_start - 1),u)));}TE IN U AbstractIntervalAddBIT::IntervalSum(CRI i_start,CRI i_final){RE m_M.Sum(m_M.Inverse(InitialSegmentSum(i_start - 1)),InitialSegmentSum(i_final));}TE IN OS& OP<<(OS& os,AbstractIntervalAddBIT& bit){auto&& SZ = bit.SZ();for(int i = 0;i < SZ;i++){(i == 0?os:os << " ")<< bit[i];}RE os;} #endif #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Mathematics/SetTheory/DirectProduct/AffineSpace/SqrtDecomposition/LazyEvaluation/a_Body.hpp" #else TE CL VirtualBiModule:VI PU UnderlyingSet{PU:VI U LAction(CO L& l,U u)= 0;VI U RAction(U u,CO R& r)= 0;IN U ScalarProduct(CO L& l,U u);IN U PW(U u,CO R& r);};TE CL AbstractBiModule:PU VirtualBiModule,PU GROUP{PU:O_U_L m_o_U_L;O_U_R m_o_U_R;IN AbstractBiModule(CO L& dummy_l,CO R& dummy_r,O_U_L o_U_L,O_U_R o_U_R,GROUP M);IN AbstractBiModule& OP=(CO AbstractBiModule&)NE;IN U LAction(CO L& l,U u);IN U RAction(U u,CO R& r);};TE AbstractBiModule(CO L& dummy_l,CO R& dummy_r,O_U_L o_U_L,O_U_R o_U_R,GROUP M)-> AbstractBiModule,O_U_L,O_U_R,GROUP>;TE CL BiModule:VI PU VirtualBiModule,PU AdditiveGroup{PU:IN U LAction(CO L& r,U u);IN U RAction(U u,CO R& r);}; TE IN AbstractBiModule::AbstractBiModule(CO L& dummy_l,CO R& dummy_r,O_U_L o_U_L,O_U_R o_U_R,GROUP M):GROUP(MO(M)),m_o_U_L(MO(o_U_L)),m_o_U_R(MO(o_U_R)){ST_AS(is_same_v> && is_invocable_r_v && is_invocable_r_v);}TE IN U AbstractBiModule::LAction(CO L& l,U u){RE m_o_U_L(l,MO(u));}TE IN U BiModule::LAction(CO L& l,U u){RE MO(u *= l);}TE IN U AbstractBiModule::RAction(U u,CO R& r){RE m_o_U_R(MO(u),r);}TE IN U BiModule::RAction(U u,CO R& r){RE MO(u *= r);}TE IN U VirtualBiModule::ScalarProduct(CO L& l,U u){RE LAction(l,MO(u));}TE IN U VirtualBiModule::PW(U u,CO R& r){RE RAction(MO(u),r);} CL SqrtDecompositionCoordinate{PU:int m_N;int m_N_sqrt;int m_N_d;int m_N_m;IN SqrtDecompositionCoordinate(CRI N = 0);IN SqrtDecompositionCoordinate(CRI N,CRI N_sqrt);ST IN int Sqrt(CRI N)NE;}; IN SqrtDecompositionCoordinate::SqrtDecompositionCoordinate(CRI N):SqrtDecompositionCoordinate(N,Sqrt(N)){};IN SqrtDecompositionCoordinate::SqrtDecompositionCoordinate(CRI N,CRI N_sqrt):m_N(N),m_N_sqrt(N_sqrt),m_N_d((m_N + m_N_sqrt - 1)/ m_N_sqrt),m_N_m(m_N_d * m_N_sqrt){}IN int SqrtDecompositionCoordinate::Sqrt(CRI N)NE{if(N <= 1){RE 1;}int l = 0,r = N;WH(l + 1 < r){int m =(l + r)>> 1;(m <=(N - 1)/ m?l:r)= m;}RE r;} #define SFINAE_FOR_SD_S enable_if_t>* TE CL LazySqrtDecomposition:PU SqrtDecompositionCoordinate{PU:PT_MAGMA m_L;RN_BIMODULE m_M;VE m_a;VE m_b;VE m_lazy_substitution;VE m_suspended;VE m_lazy_action;TE IN LazySqrtDecomposition(PT_MAGMA L,RN_BIMODULE M,CRI N = 0,CO Args&... args);TE IN LazySqrtDecomposition(PT_MAGMA L,RN_BIMODULE M,VE a,CO Args&... args);TE IN VO Initialise(Args&&... args);IN VO Set(CRI i,CO U& u);IN VO IntervalSet(CRI i_start,CRI i_final,CO U& u);IN VO IntervalAct(CRI i_start,CRI i_final,CO R& r);IN U OP[](CRI i);IN U Get(CRI i);IN U IntervalProduct(CRI i_start,CRI i_final);TE IN int Search(CRI i_start,CO F& f);IN int Search(CRI i_start,CO U& u);IN VO COruct();IN VO SetProduct(CRI i);IN VO SolveSuspendedSubstitution(CRI d,CO U& u);IN VO IntervalSet_Body(CRI i_min,CRI i_ulim,CO U& u);IN VO SolveSuspendedAction(CRI d);IN VO IntervalAct_Body(CRI i_min,CRI i_ulim,CO R& r);IN U IntervalProduct_Body(CRI i_min,CRI i_ulim);TE int Search_Body(CRI i_start,CO F& f,U product_temp);};TE LazySqrtDecomposition(PT_MAGMA L,RN_BIMODULE M,CO Args&... args)-> LazySqrtDecomposition,PT_MAGMA,inner_t,RN_BIMODULE>; TE TE IN LazySqrtDecomposition::LazySqrtDecomposition(PT_MAGMA L,RN_BIMODULE M,CRI N,CO Args&... args):SqrtDecompositionCoordinate(N,args...),m_L(MO(L)),m_M(MO(M)),m_a(N,m_M.One()),m_b(m_N_d,m_M.One()),m_lazy_substitution(m_b),m_suspended(m_N_d),m_lazy_action(m_N_d,m_L.Point()){COruct();}TE TE IN LazySqrtDecomposition::LazySqrtDecomposition(PT_MAGMA L,RN_BIMODULE M,VE a,CO Args&... args):SqrtDecompositionCoordinate(a.SZ(),args...),m_L(MO(L)),m_M(MO(M)),m_a(MO(a)),m_b(m_N_d,m_M.One()),m_lazy_substitution(m_b),m_suspended(m_N_d),m_lazy_action(m_N_d,m_L.Point()){COruct();}TE IN VO LazySqrtDecomposition::COruct(){ST_AS(is_same_v> && is_same_v>);m_a.resize(m_N_m,m_M.One());int i_min = 0;int i_ulim = m_N_sqrt;for(int d = 0;d < m_N_d;d++){U& m_bd = m_b[d];for(int i = i_min;i < i_ulim;i++){m_bd = m_M.Product(MO(m_bd),m_a[i]);}i_min = i_ulim;i_ulim += m_N_sqrt;}}TE TE IN VO LazySqrtDecomposition::Initialise(Args&&...args){LazySqrtDecomposition temp{m_L,m_M,forward(args)...};SqrtDecompositionCoordinate::OP=(temp);m_a = MO(temp.m_a);m_b = MO(temp.m_b);m_lazy_substitution = MO(temp.m_lazy_substitution);m_suspended = MO(temp.m_suspended);m_lazy_action = MO(temp.m_lazy_action);}TE IN VO LazySqrtDecomposition::Set(CRI i,CO U& u){CO int d = i / m_N_sqrt;CO int i_min = d * m_N_sqrt;CO int i_ulim = i_min + m_N_sqrt;U& m_ai = m_a[i];if(m_suspended[d]){U& m_lazy_substitution_d = m_lazy_substitution[d];if(m_lazy_substitution_d != u){SolveSuspendedSubstitution(d,m_lazy_substitution_d);m_ai = u;m_b[d]= m_M.Product(m_M.Product(m_M.PW(m_lazy_substitution_d,i - i_min),u),m_M.PW(m_lazy_substitution_d,i_ulim -(i + 1)));}}else{SolveSuspendedAction(d);if(m_ai != u){m_ai = u;SetProduct(d);}}RE;}TE IN VO LazySqrtDecomposition::IntervalSet(CRI i_start,CRI i_final,CO U& u){CO int i_min = max(i_start,0);CO int i_ulim = min(i_final + 1,m_N);CO int d_0 =(i_min + m_N_sqrt - 1)/ m_N_sqrt;CO int d_1 = max(d_0,i_ulim / m_N_sqrt);CO int d_0_N_sqrt = d_0 * m_N_sqrt;CO int d_1_N_sqrt = d_1 * m_N_sqrt;CO int i_0 = min(d_0_N_sqrt,i_ulim);CO int i_1 = max(i_0,d_1_N_sqrt);if(i_min < i_0){CO int d_0_minus = d_0 - 1;CO int d_0_N_sqrt_minus = d_0_N_sqrt - m_N_sqrt;U& m_bd = m_b[d_0_minus];VE::reference m_suspended_d = m_suspended[d_0_minus];if(m_suspended_d){U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];IntervalSet_Body(d_0_N_sqrt_minus,i_min,m_lazy_substitution_d);IntervalSet_Body(i_min,i_0,u);IntervalSet_Body(i_0,d_0_N_sqrt,m_lazy_substitution_d);m_suspended_d = false;m_bd = m_M.Product(m_M.Product(m_M.PW(m_lazy_substitution_d,i_min - d_0_N_sqrt_minus),m_M.PW(u,i_0 - i_min)),m_M.PW(m_lazy_substitution_d,d_0_N_sqrt - i_0));}else{SolveSuspendedAction(d_0_minus);IntervalSet_Body(i_min,i_0,u);m_bd = m_M.Product(m_M.Product(IntervalProduct_Body(d_0_N_sqrt_minus,i_min),m_M.PW(u,i_0 - i_min)),IntervalProduct_Body(i_0,d_0_N_sqrt));}}CO U PW = m_M.PW(u,m_N_sqrt);for(int d = d_0;d < d_1;d++){m_b[d]= PW;m_lazy_substitution[d]= u;m_suspended[d]= true;m_lazy_action[d]= m_L.Point();}if(i_1 < i_ulim){CO int d_1_N_sqrt_plus = d_1_N_sqrt + m_N_sqrt;U& m_bd = m_b[d_1];VE::reference m_suspended_d = m_suspended[d_1];if(m_suspended_d){CO U& m_lazy_substitution_d = m_lazy_substitution[d_1];IntervalSet_Body(d_1_N_sqrt,i_1,m_lazy_substitution_d);IntervalSet_Body(i_1,i_ulim,u);IntervalSet_Body(i_ulim,d_1_N_sqrt_plus,m_lazy_substitution_d);m_suspended_d = false;m_bd = m_M.Product(m_M.Product(m_M.PW(m_lazy_substitution_d,i_1 - d_1_N_sqrt),m_M.PW(u,i_ulim - i_1)),m_M.PW(m_lazy_substitution_d,d_1_N_sqrt_plus - i_ulim));}else{SolveSuspendedAction(d_1);IntervalSet_Body(i_1,i_ulim,u);m_bd = m_M.Product(m_M.Product(IntervalProduct_Body(d_1_N_sqrt,i_1),m_M.PW(u,i_ulim - i_1)),IntervalProduct_Body(i_ulim,d_1_N_sqrt_plus));}}RE;}TE IN VO LazySqrtDecomposition::IntervalAct(CRI i_start,CRI i_final,CO R& r){if(r != m_L.Point()){CO int i_min = max(i_start,0);CO int i_ulim = min(i_final + 1,m_N);CO int d_0 =(i_min + m_N_sqrt - 1)/ m_N_sqrt;CO int d_1 = max(d_0,i_ulim / m_N_sqrt);CO int d_0_N_sqrt = d_0 * m_N_sqrt;CO int d_1_N_sqrt = d_1 * m_N_sqrt;CO int i_0 = min(d_0_N_sqrt,i_ulim);CO int i_1 = max(i_0,d_1_N_sqrt);if(i_min < i_0){CO int d_0_minus = d_0 - 1;CO int d_0_N_sqrt_minus = d_0_N_sqrt - m_N_sqrt;VE::reference m_suspended_d = m_suspended[d_0_minus];if(m_suspended_d){CO U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];U& m_bd = m_b[d_0_minus];CO U u = m_M.ScalarProduct(r,m_lazy_substitution_d);IntervalSet_Body(d_0_N_sqrt_minus,i_min,m_lazy_substitution_d);IntervalSet_Body(i_min,i_0,u);IntervalSet_Body(i_0,d_0_N_sqrt,m_lazy_substitution_d);m_suspended_d = false;m_bd = m_M.Product(m_M.Product(m_M.PW(m_lazy_substitution_d,i_min - d_0_N_sqrt_minus),m_M.PW(u,i_0 - i_min)),m_M.PW(m_lazy_substitution_d,d_0_N_sqrt - i_0));}else{R& m_lazy_action_d = m_lazy_action[d_0_minus];if(m_lazy_action_d == m_L.Point()){IntervalAct_Body(i_min,i_0,r);}else{IntervalAct_Body(d_0_N_sqrt_minus,i_min,m_lazy_action_d);IntervalAct_Body(i_min,i_0,m_L.Product(r,m_lazy_action_d));IntervalAct_Body(i_0,d_0_N_sqrt,m_lazy_action_d);m_lazy_action_d = m_L.Point();}SetProduct(d_0_minus);}}for(int d = d_0;d < d_1;d++){U& m_bd = m_b[d];m_bd = m_M.ScalarProduct(r,m_bd);if(m_suspended[d]){U& m_lazy_substitution_d = m_lazy_substitution[d];m_lazy_substitution_d = m_M.ScalarProduct(r,m_lazy_substitution_d);}else{R& m_lazy_action_d = m_lazy_action[d];m_lazy_action_d = m_L.Product(r,m_lazy_action_d);}}if(i_1 < i_ulim){CO int d_1_N_sqrt_plus = d_1_N_sqrt + m_N_sqrt;VE::reference m_suspended_d = m_suspended[d_1];if(m_suspended_d){CO U& m_lazy_substitution_d = m_lazy_substitution[d_1];U& m_bd = m_b[d_1];CO U u = m_M.ScalarProduct(r,m_lazy_substitution_d);IntervalSet_Body(d_1_N_sqrt,i_1,m_lazy_substitution_d);IntervalSet_Body(i_1,i_ulim,u);IntervalSet_Body(i_ulim,d_1_N_sqrt_plus,m_lazy_substitution_d);m_suspended_d = false;m_bd = m_M.Product(m_M.Product(m_M.PW(m_lazy_substitution_d,i_1 - d_1_N_sqrt),m_M.PW(u,i_ulim - i_1)),m_M.PW(m_lazy_substitution_d,d_1_N_sqrt_plus - i_ulim));}else{R& m_lazy_action_d = m_lazy_action[d_1];if(m_lazy_action_d == m_L.Point()){IntervalAct_Body(i_1,i_ulim,r);SetProduct(d_1);}else{IntervalAct_Body(d_1_N_sqrt,i_1,m_lazy_action_d);IntervalAct_Body(i_1,i_ulim,m_L.Product(r,m_lazy_action_d));IntervalAct_Body(i_ulim,d_1_N_sqrt_plus,m_lazy_action_d);m_lazy_action_d = m_L.Point();SetProduct(d_1);}}}}RE;}TE IN U LazySqrtDecomposition::IntervalProduct_Body(CRI i_min,CRI i_ulim){U AN = m_M.One();for(int i = i_min;i < i_ulim;i++){AN = m_M.Product(MO(AN),m_a[i]);}RE AN;}TE IN VO LazySqrtDecomposition::SetProduct(CRI d){U& m_bd = m_b[d]= m_M.One();CO int i_min = d * m_N_sqrt;CO int i_ulim = i_min + m_N_sqrt;for(int i = i_min;i < i_ulim;i++){m_bd = m_M.Product(MO(m_bd),m_a[i]);}RE;}TE IN VO LazySqrtDecomposition::SolveSuspendedSubstitution(CRI d,CO U& u){CO int i_min = d * m_N_sqrt;IntervalSet_Body(i_min,i_min + m_N_sqrt,u);m_suspended[d]= false;RE;}TE IN VO LazySqrtDecomposition::IntervalSet_Body(CRI i_min,CRI i_ulim,CO U& u){for(int i = i_min;i < i_ulim;i++){m_a[i]= u;}RE;}TE IN VO LazySqrtDecomposition::SolveSuspendedAction(CRI d){R& m_lazy_action_d = m_lazy_action[d];if(m_lazy_action_d != m_L.Point()){CO int i_min = d * m_N_sqrt;CO int i_ulim = i_min + m_N_sqrt;IntervalAct_Body(i_min,i_ulim,m_lazy_action_d);U& m_bd = m_b[d];m_bd = m_M.ScalarProduct(m_lazy_action_d,m_bd);m_lazy_action_d = m_L.Point();}RE;}TE IN U LazySqrtDecomposition::OP[](CRI i){AS(0 <= i && i < m_N);CO int d = i / m_N_sqrt;RE m_suspended[d]?m_lazy_substitution[d]:m_M.ScalarProduct(m_lazy_action[d],m_a[i]);}TE IN U LazySqrtDecomposition::Get(CRI i){RE OP[](i);}TE IN U LazySqrtDecomposition::IntervalProduct(CRI i_start,CRI i_final){CO int i_min = max(i_start,0);CO int i_ulim = min(i_final + 1,m_N);CO int d_0 =(i_min + m_N_sqrt - 1)/ m_N_sqrt;CO int d_1 = max(d_0,i_ulim / m_N_sqrt);CO int i_0 = min(d_0 * m_N_sqrt,i_ulim);CO int i_1 = max(i_0,d_1 * m_N_sqrt);U AN = m_M.One();if(i_min < i_0){CO int d_0_minus = d_0 - 1;AN = m_suspended[d_0_minus]?m_M.PW(m_lazy_substitution[d_0_minus],i_0 - i_min):m_M.ScalarProduct(m_lazy_action[d_0_minus],IntervalProduct_Body(i_min,i_0));}for(int d = d_0;d < d_1;d++){AN = m_M.Product(MO(AN),m_b[d]);}if(i_1 < i_ulim){AN = m_M.Product(MO(AN),m_suspended[d_1]?m_M.PW(m_lazy_substitution[d_1],i_ulim - i_1):m_M.ScalarProduct(m_lazy_action[d_1],IntervalProduct_Body(i_1,i_ulim)));}RE AN;}TE IN VO LazySqrtDecomposition::IntervalAct_Body(CRI i_min,CRI i_ulim,CO R& r){for(int i = i_min;i < i_ulim;i++){U& m_ai = m_a[i];m_ai = m_M.ScalarProduct(r,m_ai);}RE;}TE TE IN int LazySqrtDecomposition::Search(CRI i_start,CO F& f){RE Search_Body(i_start,f,m_M.One());}TE IN int LazySqrtDecomposition::Search(CRI i_start,CO U& u){RE Search(i_start,[&](CO U& product,CRI){RE !(product < u);});}TE TE int LazySqrtDecomposition::Search_Body(CRI i_start,CO F& f,U product_temp){CO int i_min = max(i_start,0);CO int d_0 = i_min / m_N_sqrt + 1;CO int i_0 = min(d_0 * m_N_sqrt,m_N);if(i_min < i_0){CO int d_0_minus = d_0 - 1;if(m_suspended[d_0_minus]){SolveSuspendedSubstitution(d_0_minus,m_lazy_substitution[d_0_minus]);}else if(m_lazy_action[d_0_minus]!= m_L.Point()){SolveSuspendedAction(d_0_minus);}}for(int i = i_min;i < i_0;i++){product_temp = m_M.Product(MO(product_temp),m_a[i]);if(f(product_temp,i)){RE i;}}for(int d = d_0;d < m_N_d;d++){U product_next = m_M.Product(product_temp,m_b[d]);if(f(product_next,min((d + 1)* m_N_sqrt,m_N)- 1)){RE Search_Body(d * m_N_sqrt,f,product_temp);}product_temp = MO(product_next);}RE -1;} #endif #ifdef DEBUG #include "c:/Users/user/Documents/Programming/Utility/String/RollingHash/Shift/BiModule/a_Body.hpp" #else TE >CL RollingHash{PU:INT m_SZ;MODINT m_r;MODINT m_r_inv;VE m_r_pw;IN RollingHash();IN RollingHash(MODINT r);IN CO MODINT& r()CO NE;IN CO MODINT& r_inv()CO NE;IN CO VE& r_pw()CO NE;TE IN CODE Encode(CO STR& s,CO bool& reversed = false);TE IN VE

 CumulativeEncode(CO STR& s,CO bool& reversed = false);TE  IN VE PointwiseEncode(CO STR& s,CO bool& reversed = false);TE  IN VE FixedLengthEncode(CO STR& s,CRI le,CO bool& reversed = false);TE  IN CODE Replace(CODE code,CO INT& i,CO CHAR& c_prev,CO CHAR& c_next)CO;TE  IN CODE PopFront(CODE code,CO CHAR& c_prev)CO;TE  IN CODE PopBack(CODE code,CO CHAR& c_prev)CO;TE  IN INT CountContain(CO STR& s,CO CODE& code,CO bool& reversed = false);ST IN CODE Concatenate(CODE code0,CO CODE& code1);ST IN CODE Fold(CODE code,INT n);MODINT GetRand();VO CheckSize(CO INT& SZ);VI MODINT Twist(CRL c);};
TE  IN RollingHash::RollingHash():RollingHash(GetRand()){}TE  IN RollingHash::RollingHash(MODINT r):m_SZ(1),m_r(MO(r)),m_r_inv(m_r),m_r_pw{1}{m_r_inv.Invert();}TE  IN CO MODINT& RollingHash::r()CO NE{RE m_r;}TE  IN CO MODINT& RollingHash::r_inv()CO NE{RE m_r_inv;}TE  IN CO VE& RollingHash::r_pw()CO NE{RE m_r_pw;}TE  TE  IN CODE RollingHash::Encode(CO STR& s,CO bool& reversed){CO int SZ = s.SZ();CheckSize(SZ + 1);MODINT AN = 0;for(int i = 0;i < SZ;i++){AN += Twist(s[reversed?SZ - 1 - i:i])* m_r_pw[i];}RE{AN,m_r_pw[SZ],SZ};}TE  TE  IN VE RollingHash::CumulativeEncode(CO STR& s,CO bool& reversed){CO int SZ = s.SZ();CheckSize(SZ + 1);VE AN(SZ + 1);for(int i = 0;i < SZ;i++){AN[i+1]= Concatenate(AN[i],{Twist(s[reversed?SZ - 1 - i:i])* m_r_pw[i],m_r,1});}RE AN;}TE  TE  IN VE RollingHash::PointwiseEncode(CO STR& s,CO bool& reversed){CO int SZ = s.SZ();CheckSize(SZ + 1);VE AN(SZ);for(int i = 0;i < SZ;i++){AN[i]={Twist(s[reversed?SZ - 1 - i:i]),m_r,1};}RE AN;}TE  TE  IN VE RollingHash::FixedLengthEncode(CO STR& s,CRI le,CO bool& reversed){CO int SZ = s.SZ();VE AN{};if(le <= SZ){CheckSize(le + 1);AN.resize(SZ - le + 1,{MODINT{},m_r_pw[le],1});for(int i = 0;i < le;i++){get<0>(AN[0])+= Twist(s[reversed?SZ - 1 - i:i])* m_r_pw[i];}CO int SZ_shifted = SZ - le;for(int i = 1;i <= SZ_shifted;i++){get<0>(AN[i])=(get<0>(AN[i-1])- e(s[reversed?SZ - i:i - 1]))* m_r_inv + e(s[reversed?SZ - i - le:i - 1 + le])* m_r_pw[le-1];}}RE AN;}TE  TE  IN CODE RollingHash::Replace(CODE code,CO INT& i,CO CHAR& c_prev,CO CHAR& c_next)CO{auto&[h,p,s]= code;AS(i < s);h +=(Twist(c_next)-= Twist(c_prev))*=(i < m_SZ?m_r_pw[i]:R_Power(m_r,i));RE MO(code);}TE  TE  IN CODE RollingHash::PopFront(CODE code,CO CHAR& c_prev)CO{auto&[h,p,s]= code;AS(s-- > 0);h -= Twist(c_prev)*(s < m_SZ?m_r_pw[s]:R_Power(m_r,s));r *= m_r_inv;RE MO(code);}TE  TE  IN CODE RollingHash::PopBack(CODE code,CO CHAR& c_prev)CO{auto&[h,p,s]= code;AS(s-- > 0);(h -= Twist(c_prev)* m_r_pw[0])*= m_r_inv;r *= m_r_inv;RE MO(code);}TE  TE  IN INT RollingHash::CountContain(CO STR& s,CO CODE& code,CO bool& reversed){CO INT SZ0 = s.SZ();CheckSize(SZ0);CO MODINT& n = get<0>(code);CO INT& SZ1 = get<2>(code);if(SZ1 == 0){RE 1;}CheckSize(SZ1);CO MODINT& r_pw = m_r_pw[SZ1 - 1];INT AN = 0;MODINT temp = 0;for(INT i = 0;i < SZ0;i++){(i < SZ1?temp += e(s[reversed?SZ0 - 1 - i:i])* m_r_pw[i]:((temp -= Twist(s[reversed?SZ0 + SZ1 - 1 - i:i - SZ1]))*= m_r_inv)+= Twist(s[reversed?SZ0 - 1 - i:i])* r_pw)== n?++AN:AN;}RE AN;}TE  IN CODE RollingHash::Concatenate(CODE code0,CO CODE& code1){auto&[h,p,s]= code0;h += get<0>(code1)* p;p *= get<1>(code1);s += get<2>(code1);RE MO(code0);}TE  IN CODE RollingHash::Fold(CODE code,INT n){AS(n >= 0);CODE AN{0,1,0};auto&[h,p,s]= code;WH(n > 0){(n & 1)== 1?AN = Concatenate(MO(AN),code):AN;h *= p + 1;p *= p;s += s;n >>= 1;}RE AN;}TE  MODINT RollingHash::GetRand(){RE::GetRand(((MODINT{}- 1)/ 11).RP(),(MODINT{}- 1).RP());}TE  VO RollingHash::CheckSize(CO INT& SZ){WH(m_SZ < SZ){m_r_pw.push_back(m_r_pw[m_SZ++ - 1]* m_r);}}TE  MODINT RollingHash::Twist(CRL c){RE MODINT(c);}

TE ,TY INT = int,TY CODE = tuple>CL ShiftableRollingHash:PU RollingHash{PU:MODINT m_twist[26];ST CE CO MODINT m_pw[26]={MODINT::DeRP(1),MODINT::DeRP(1102168),MODINT::DeRP(613375579),MODINT::DeRP(130931742),MODINT::DeRP(503948232),MODINT::DeRP(461900919),MODINT::DeRP(232590460),MODINT::DeRP(920965690),MODINT::DeRP(393424640),MODINT::DeRP(711779163),MODINT::DeRP(364175458),MODINT::DeRP(920693367),MODINT::DeRP(40549276),MODINT::DeRP(999309402),MODINT::DeRP(998207235),MODINT::DeRP(385933824),MODINT::DeRP(868377661),MODINT::DeRP(495361171),MODINT::DeRP(537408484),MODINT::DeRP(766718943),MODINT::DeRP(78343713),MODINT::DeRP(605884763),MODINT::DeRP(287530240),MODINT::DeRP(635133945),MODINT::DeRP(78616036),MODINT::DeRP(958760127)};IN ShiftableRollingHash();IN CODE Shift(CO Mod<26>& shift,CODE c)CO;MODINT Twist(CRL c);};
TE  IN ShiftableRollingHash::ShiftableRollingHash():RollingHash(),m_twist{TH->GetRand()}{for(int i = 1;i < 26;i++){m_twist[i]= m_twist[0]* m_pw[i];}}TE  IN CODE ShiftableRollingHash::Shift(CO Mod<26>& shift,CODE c)CO{get<0>(c)*= m_pw[shift.RP()];RE MO(c);}TE  MODINT ShiftableRollingHash::Twist(CRL c){AS('A' <= c && c <= 'z');RE m_twist[c -(c < 'a'?'A':'a')];}

TE ,TY INT = int,TY CODE = tuple>CL ShiftableRollingHashBiModule:PU PointedSet,VI PU VirtualGroup,VI PU VirtualBiModule,int,CODE>{PU:CO ShiftableRollingHash* m_p_srh;IN ShiftableRollingHashBiModule(CO ShiftableRollingHash& srh);IN CODE Product(CODE code0,CO CODE& code1);IN CODE Transfer(CO CODE& code);IN CODE LAction(CO Mod<26>& l,CODE code);IN CODE RAction(CODE code,CRI r);};
TE  IN ShiftableRollingHashBiModule::ShiftableRollingHashBiModule(CO ShiftableRollingHash& srh):PointedSet({0,1,0}),m_p_srh{&srh}{ST_AS(is_same_v>);}TE  IN CODE ShiftableRollingHashBiModule::Product(CODE code0,CO CODE& code1){RE ShiftableRollingHash::Concatenate(MO(code0),code1);}TE  IN CODE ShiftableRollingHashBiModule::Transfer(CO CODE& code){MODINT p = 1 / get<1>(code);RE{- get<0>(code)* p,p,-get<2>(code)};}TE  IN CODE ShiftableRollingHashBiModule::LAction(CO Mod<26>& l,CODE code){RE m_p_srh->Shift(l,MO(code));}TE  IN CODE ShiftableRollingHashBiModule::RAction(CODE code,CRI r){RE ShiftableRollingHash::Fold(MO(code),r);}
#endif

/* AAA 常設でないライブラリは以上に挿入する。*/

#define INCLUDE_SUB
#include __FILE__
#else /* INCLUDE_LIBRARY */
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if CE( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } FINISH_MAIN
  #define FINISH_MAIN REPEAT( test_case_num ){ if CE( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } }
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 )
  #define ASSERT( A , MIN , MAX ) AS( ( MIN ) <= A && A <= ( MAX ) )
  #ifdef USE_GETLINE
    #define SET_SEPARATE( SEPARATOR , ... ) VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
    #define SET( ... ) SET_SEPARATE( '\n' , __VA_ARGS__ )
    #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; SET_SEPARATE( SEPARATOR , __VA_ARGS__ )
    #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
  #else
    #define SET( ... ) VariadicCin( cin , __VA_ARGS__ )
    #define CIN( LL , ... ) LL __VA_ARGS__; SET( __VA_ARGS__ )
    #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); }
    #define CIN_A( LL , I , N , ... ) VE __VA_ARGS__; SET_A( I , N , __VA_ARGS__ )
    #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) VE> VAR( N0 + I0 ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); }
  #endif
  #define SET_ASSERT( A , MIN , MAX ) SET( A ); ASSERT( A , MIN , MAX )
  #define SOLVE_ONLY 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL
  #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ )
  #define CERR( ... ) 
  #define CERRNS( ... ) 
  #define COUT_A( I , N , A ) CoutArray( cout , I , N , A ) << ENDL
  #define CERR_A( I , N , A ) 
#endif
#ifdef REACTIVE
  #ifdef DEBUG
    #define RSET( A , ... ) A = __VA_ARGS__
  #else
    #define RSET( A , ... ) SET( A )
  #endif
  #define RCIN( LL , A , ... ) LL A; RSET( A , __VA_ARGS__ )
  #define ENDL endl
#else
  #define ENDL "\n"
#endif
#include 
using namespace std;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now(); double loop_average_time = 0.0 , loop_start_time = 0.0 , current_time = 0.0; int loop_count = 0
#define CURRENT_TIME ( current_time = static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME , loop_count == 0 ? loop_start_time = current_time : loop_average_time = ( current_time - loop_start_time ) / loop_count , ++loop_count , current_time < TL_MS - loop_average_time * 2 - 100.0 )
#define CEXPR( LL , BOUND , VALUE ) CE LL BOUND = VALUE
#define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); }
#define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } }
#define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX )
#define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX )
#define OUTPUT_ARRAY( C , I , N , A ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , I , N ){ C << A[VARIABLE_FOR_OUTPUT_ARRAY] << " \n"[VARIABLE_FOR_OUTPUT_ARRAY==(N)-1]; }
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- )
#define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN()
#define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ); cerr << fixed << setprecision( DECIMAL_DIGITS )
#define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); RE
#define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ , true ); auto answer = Answer( __VA_ARGS__ ); bool match = naive == answer; CERR( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Naive == " , naive , match ? "==" : "!=" , answer , "== Answer" ); if( !match ){ RE; }

/* 圧縮用 */
#define TE template
#define TY typename
#define US using
#define ST static
#define AS assert
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define LE length
#define PW Power
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define VI virtual 
#define IS basic_istream
#define OS basic_ostream
#define ST_AS static_assert
#define reMO_CO remove_const
#define is_COructible_v is_constructible_v
#define rBE rbegin

/* 型のエイリアス */
#define decldecay_t(VAR)decay_t
TE  US ret_t = decltype(declval()(declval()...));
TE  US inner_t = TY T::type;
US uint = unsigned int;
US ll = long long;
US ull = unsigned long long;
US ld = long double;
US lld = __float128;
TE  US T2 = pair;
TE  US T3 = tuple;
TE  US T4 = tuple;
US path = pair;

/* VVV 常設ライブラリは以下に挿入する。*/
#ifdef DEBUG
  #include "C:/Users/user/Documents/Programming/Contest/Template/Local/a_Body.hpp"
#else
/* Random (1KB)*/
ll GetRand(CRI Rand_min,CRI Rand_max){AS(Rand_min <= Rand_max);ll AN = time(NULL);RE AN * rand()%(Rand_max + 1 - Rand_min)+ Rand_min;}

/* Set (1KB)*/
#define DC_OF_HASH(...)struct hash<__VA_ARGS__>{IN size_t OP()(CO __VA_ARGS__& n)CO;};
CL is_ordered{PU:is_ordered()= delete;TE  ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE  ST CE CO bool value = is_same_v< decltype(Check(declval())),true_type >;};
TE US Set = conditional_t>,unordered_set,conditional_t,set,VO>>;

/* Tuple (5KB)*/
#define DF_OF_AR_FOR_TUPLE(OPR)TE  TY V> IN auto OP OPR ## =(V& t0,CO V& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);RE t0;}TE  IN tuple& OP OPR ## =(tuple& t0,CO tuple& t1){get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);get<2>(t0)OPR ## = get<2>(t1);RE t0;}TE  IN tuple& OP OPR ## =(tuple& t0,CO tuple& t1){get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);get<2>(t0)OPR ## = get<2>(t1);get<3>(t0)OPR ## = get<3>(t1);RE t0;}TE  TY V> IN auto OP OPR ## =(V& t0,CO ARG& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;RE t0;}TE  IN tuple& OP OPR ## =(tuple& t0,CO ARG& t1){get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;get<2>(t0)OPR ## = t1;RE t0;}TE  IN tuple& OP OPR ## =(tuple& t0,CO ARG& t1){get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;get<2>(t0)OPR ## = t1;get<3>(t0)OPR ## = t1;RE t0;}TE  TY V,TY...ARGS,TY ARG> IN auto OP OPR(CO V& t0,CO ARG& t1)-> decldecay_t((get<0>(t0),t0)){auto t = t0;RE MO(t OPR ## = t1);}
#define DF_OF_INCREMENT_FOR_TUPLE(INCR)TE  TY V> IN auto OP INCR(V& t)-> decltype((get<0>(t),t))&{INCR get<0>(t);INCR get<1>(t);RE t;}TE  IN tuple& OP INCR(tuple& t){INCR get<0>(t);INCR get<1>(t);INCR get<2>(t);RE t;}TE  IN tuple& OP INCR(tuple& t){INCR get<0>(t);INCR get<1>(t);INCR get<2>(t);INCR get<3>(t);RE t;}
TE  IN IS& OP>>(IS& is,tuple& arg){RE is >> get<0>(arg);}TE  TY V> IN auto OP>>(IS& is,V& arg)-> decltype((get<0>(arg),is))&{RE is >> get<0>(arg)>> get<1>(arg);}TE  IN IS& OP>>(IS& is,tuple& arg){RE is >> get<0>(arg)>> get<1>(arg)>> get<2>(arg);}TE  IN IS& OP>>(IS& is,tuple& arg){RE is >> get<0>(arg)>> get<1>(arg)>> get<2>(arg)>> get<3>(arg);}TE  IN OS& OP<<(OS& os,CO tuple& arg){RE os << get<0>(arg);}TE  TY V> IN auto OP<<(OS& os,CO V& arg)-> decltype((get<0>(arg),os))&{RE os << get<0>(arg)<< " " << get<1>(arg);}TE  IN OS& OP<<(OS& os,CO tuple& arg){RE os << get<0>(arg)<< " " << get<1>(arg)<< " " << get<2>(arg);}TE  IN OS& OP<<(OS& os,CO tuple& arg){RE os << get<0>(arg)<< " " << get<1>(arg)<< " " << get<2>(arg)<< " " << get<3>(arg);}DF_OF_AR_FOR_TUPLE(+);TE  TY V> IN auto OP-(CO V& t)-> decltype(get<0>(t),t){RE{-get<0>(t),-get<1>(t)};}TE  IN tuple OP-(CO tuple& t){RE{-get<0>(t),-get<1>(t),-get<2>(t)};}TE  IN tuple OP-(CO tuple& t){RE{-get<0>(t),-get<1>(t),-get<2>(t),-get<3>(t)};}DF_OF_AR_FOR_TUPLE(-);DF_OF_AR_FOR_TUPLE(*);DF_OF_AR_FOR_TUPLE(/);DF_OF_AR_FOR_TUPLE(%);DF_OF_INCREMENT_FOR_TUPLE(++);DF_OF_INCREMENT_FOR_TUPLE(--);

#define DF_OF_HASH_FOR_TUPLE(PAIR)TE  IN size_t hash>::OP()(CO PAIR& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash h0;ST CO hash h1;RE(h0(get<0>(n))* seed)^ h1(get<1>(n));}
TE  DC_OF_HASH(tuple);TE  DC_OF_HASH(pair);TE  DC_OF_HASH(tuple);TE  DC_OF_HASH(tuple);TE  DC_OF_HASH(tuple);
TE  IN size_t hash>::OP()(CO tuple& n)CO{ST CO hash h;RE h(get<0>(n));}DF_OF_HASH_FOR_TUPLE(pair);DF_OF_HASH_FOR_TUPLE(tuple);TE  IN size_t hash>::OP()(CO tuple& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash> h01;ST CO hash h2;RE(h01({get<0>(n),get<1>(n)})* seed)^ h2(get<2>(n));}TE  IN size_t hash>::OP()(CO tuple& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash> h01;ST CO hash> h23;RE(h01({get<0>(n),get<1>(n)})* seed)^ h23({get<2>(n),get<3>(n)});}

/* Vector (2KB)*/
#define DF_OF_COUT_FOR_VE(V)TE  IN OS& OP<<(OS& os,CO V& arg){auto BE = arg.BE(),EN = arg.EN();auto IT = BE;WH(IT != EN){(IT == BE?os:os << " ")<< *IT;IT++;}RE os;}
#define DF_OF_AR_FOR_VE(V,OPR)TE  IN V& OP OPR ## =(V& a,CO T& t){for(auto& s:a){s OPR ## = t;}RE a;}TE  IN V& OP OPR ## =(V& a0,CO V& a1){AS(a0.SZ()<= a1.SZ());auto IT0 = a0.BE(),EN0 = a0.EN();auto IT1 = a1.BE();WH(IT0 != EN0){*(IT0++)OPR ## = *(IT1++);}RE a0;}TE  IN V OP OPR(V a,CO U& u){RE MO(a OPR ## = u);}
#define DF_OF_INCREMENT_FOR_VE(V,INCR)TE  IN V& OP INCR(V& a){for(auto& i:a){INCR i;}RE a;}
#define DF_OF_ARS_FOR_VE(V)DF_OF_AR_FOR_VE(V,+);DF_OF_AR_FOR_VE(V,-);DF_OF_AR_FOR_VE(V,*);DF_OF_AR_FOR_VE(V,/);DF_OF_AR_FOR_VE(V,%);DF_OF_INCREMENT_FOR_VE(V,++);DF_OF_INCREMENT_FOR_VE(V,--);TE  IN V OP*(CO T& scalar,V v){for(auto& t:v){t *= scalar;}RE MO(v);}
DF_OF_COUT_FOR_VE(VE);DF_OF_COUT_FOR_VE(LI);DF_OF_ARS_FOR_VE(VE);DF_OF_ARS_FOR_VE(LI);IN VO VariadicResize(CRI SZ){}TE  IN VO VariadicResize(CRI SZ,Arg& arg,ARGS&... args){arg.resize(SZ);VariadicResize(SZ,args...);}TE  IN auto Get(V& a){RE[&](CRI i = 0)-> CO decldecay_t(a[0])&{RE a[i];};}TE  IN VE id(CRI SZ){VE AN(SZ);FOR(i,0,SZ){AN[i]= i;}RE AN;}TE  VO Sort(VE& a,CO bool& reversed = false){if(reversed){ST auto comp =[](CO T& t0,CO T& t1){RE t1 < t0;};sort(a.BE(),a.EN(),comp);}else{sort(a.BE(),a.EN());}}TE  IN VE IndexSort(CO VE& a,CO bool& reversed = false){auto index = id(a.SZ());if(reversed){sort(index.BE(),index.EN(),[&](CRI i,CRI j){RE a[j]< a[i];});}else{sort(index.BE(),index.EN(),[&](CRI i,CRI j){RE a[i]< a[j];});}RE index;}TE  IN U Sum(CO VE& a){U AN{};for(auto& x:a){AN += x;}RE AN;}TE  IN U Product(CO VE& a){U AN{};for(auto& x:a){AN *= x;}RE AN;}

/* Map (1KB)*/
#define DF_OF_AR_FOR_MAP(MAP,OPR)TE  IN MAP& OP OPR ## =(MAP& a,CO pair& v){a[v.first]OPR ## = v.second;RE a;}TE  IN MAP& OP OPR ## =(MAP& a0,CO MAP& a1){for(auto&[t,u]:a1){a0[t]OPR ## = u;}RE a0;}TE  IN MAP OP OPR(MAP a,CO ARG& arg){RE MO(a OPR ## = arg);}
#define DF_OF_ARS_FOR_MAP(MAP)DF_OF_AR_FOR_MAP(MAP,+);DF_OF_AR_FOR_MAP(MAP,-);DF_OF_AR_FOR_MAP(MAP,*);DF_OF_AR_FOR_MAP(MAP,/);DF_OF_AR_FOR_MAP(MAP,%);
TE US Map = conditional_t>,unordered_map,conditional_t,map,VO>>;
DF_OF_ARS_FOR_MAP(map);DF_OF_ARS_FOR_MAP(unordered_map);

/* StdStream (2KB)*/
TE  IN IS& VariadicCin(IS& is){RE is;}TE  IN IS& VariadicCin(IS& is,Arg& arg,ARGS&... args){RE VariadicCin(is >> arg,args...);}TE  IN IS& VariadicSet(IS& is,CRI i){RE is;}TE  IN IS& VariadicSet(IS& is,CRI i,Arg& arg,ARGS&... args){RE VariadicSet(is >> arg[i],i,args...);}TE  IN IS& VariadicGetline(IS& is,CO char& separator){RE is;}TE  IN IS& VariadicGetline(IS& is,CO char& separator,Arg& arg,ARGS&... args){RE VariadicGetline(getline(is,arg,separator),separator,args...);}TE  IN OS& VariadicCout(OS& os,Arg&& arg){RE os << forward(arg);}TE  IN OS& VariadicCout(OS& os,Arg1&& arg1,Arg2&& arg2,ARGS&&... args){RE VariadicCout(os << forward(arg1)<< " ",forward(arg2),forward(args)...);}TE  IN OS& VariadicCoutNonSep(OS& os,Arg&& arg){RE os << forward(arg);}TE  IN OS& VariadicCoutNonSep(OS& os,Arg1&& arg1,Arg2&& arg2,ARGS&&... args){RE VariadicCoutNonSep(os << forward(arg1),forward(arg2),forward(args)...);}TE  IN OS& CoutArray(OS& os,CRI i_start,CRI i_ulim,ARRAY&& a){for(int i = i_start;i < i_ulim;i++){(i == i_start?os:(os << " "))<< a[i];}RE os;}

/* Module (6KB)*/
#define DC_OF_CPOINT(POINT)IN CO U& POINT()CO NE
#define DC_OF_POINT(POINT)IN U& POINT()NE
#define DF_OF_CPOINT(POINT)TE  IN CO U& VirtualPointedSet::POINT()CO NE{RE Point();}
#define DF_OF_POINT(POINT)TE  IN U& VirtualPointedSet::POINT()NE{RE Point();}
TE CL UnderlyingSet{PU:US type = U;};TE CL VirtualPointedSet:VI PU UnderlyingSet{PU:VI CO U& Point()CO NE = 0;VI U& Point()NE = 0;DC_OF_CPOINT(Unit);DC_OF_CPOINT(Zero);DC_OF_CPOINT(One);DC_OF_CPOINT(Infty);DC_OF_POINT(init);DC_OF_POINT(root);};TE CL PointedSet:VI PU VirtualPointedSet{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE CL VirtualNSet:VI PU UnderlyingSet{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE CL AbstractNSet:VI PU VirtualNSet{PU:F_U m_f_U;IN AbstractNSet(F_U f_U);IN AbstractNSet& OP=(CO AbstractNSet&)NE;IN U Transfer(CO U& u);};TE CL VirtualMagma:VI PU UnderlyingSet{PU:VI U Product(U u0,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE CL AdditiveMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL MultiplicativeMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL AbstractMagma:VI PU VirtualMagma{PU:M_U m_m_U;IN AbstractMagma(M_U m_U);IN AbstractMagma& OP=(CO AbstractMagma&)NE;IN U Product(U u0,CO U& u1);};
TE  IN PointedSet::PointedSet(U b_U):m_b_U(MO(b_U)){}TE  IN CO U& PointedSet::Point()CO NE{RE m_b_U;}TE  IN U& PointedSet::Point()NE{RE m_b_U;}DF_OF_CPOINT(Unit);DF_OF_CPOINT(Zero);DF_OF_CPOINT(One);DF_OF_CPOINT(Infty);DF_OF_POINT(init);DF_OF_POINT(root);TE  IN AbstractNSet::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v);}TE  IN AbstractNSet& AbstractNSet::operator=(CO AbstractNSet&)NE{RE *TH;}TE  IN U AbstractNSet::Transfer(CO U& u){RE m_f_U(u);}TE  IN U VirtualNSet::Inverse(CO U& u){RE Transfer(u);}TE  IN AbstractMagma::AbstractMagma(M_U m_U):m_m_U(MO(m_U)){ST_AS(is_invocable_r_v);}TE  IN AbstractMagma& AbstractMagma::OP=(CO AbstractMagma&)NE{RE *TH;}TE  IN U AdditiveMagma::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE  IN U MultiplicativeMagma::Product(U u0,CO U& u1){RE MO(u0 *= u1);}TE  IN U AbstractMagma::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE  IN U VirtualMagma::Sum(U u0,CO U& u1){RE Product(MO(u0),u1);}

TE CL VirtualMonoid:VI PU VirtualMagma,VI PU VirtualPointedSet{};TE CL AdditiveMonoid:VI PU VirtualMonoid,PU AdditiveMagma,PU PointedSet{};TE CL MultiplicativeMonoid:VI PU VirtualMonoid,PU MultiplicativeMagma,PU PointedSet{PU:IN MultiplicativeMonoid(U e_U);};TE CL AbstractMonoid:VI PU VirtualMonoid,PU AbstractMagma,PU PointedSet{PU:IN AbstractMonoid(M_U m_U,U e_U);};
TE  IN MultiplicativeMonoid::MultiplicativeMonoid(U e_U):PointedSet(MO(e_U)){}TE  IN AbstractMonoid::AbstractMonoid(M_U m_U,U e_U):AbstractMagma(MO(m_U)),PointedSet(MO(e_U)){}

TE CL VirtualGroup:VI PU VirtualMonoid,VI PU VirtualPointedSet,VI PU VirtualNSet{};TE CL AdditiveGroup:VI PU VirtualGroup,PU AdditiveMonoid{PU:IN U Transfer(CO U& u);};TE CL AbstractGroup:VI PU VirtualGroup,PU AbstractMonoid,PU AbstractNSet{PU:IN AbstractGroup(M_U m_U,U e_U,I_U i_U);};
TE  IN AbstractGroup::AbstractGroup(M_U m_U,U e_U,I_U i_U):AbstractMonoid(MO(m_U),MO(e_U)),AbstractNSet(MO(i_U)){}TE  IN U AdditiveGroup::Transfer(CO U& u){RE -u;}

TE CL VirtualRSet:VI PU UnderlyingSet{PU:VI U Action(CO R& r,U u)= 0;IN U PW(U u,CO R& r);IN U ScalarProduct(CO R& r,U u);};TE CL RegularRSet:VI PU VirtualRSet,PU MAGMA{PU:IN RegularRSet(MAGMA magma);IN U Action(CO U& r,U u);};TE  RegularRSet(MAGMA magma)-> RegularRSet,MAGMA>;TE CL AbstractRSet:VI PU VirtualRSet{PU:O_U m_o_U;IN AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U);IN AbstractRSet& OP=(CO AbstractRSet&)NE;IN U Action(CO R& r,U u);};TE CL AbstractModule:PU AbstractRSet,PU GROUP{PU:IN AbstractModule(CO R& dummy,O_U o_U,GROUP M);};TE  AbstractModule(CO R& dummy,O_U o_U,GROUP M)-> AbstractModule,O_U,GROUP>;TE CL Module:VI PU VirtualRSet,PU AdditiveGroup{PU:IN U Action(CO R& r,U u);};
TE  IN RegularRSet::RegularRSet(MAGMA magma):MAGMA(MO(magma)){}TE  IN AbstractRSet::AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U):m_o_U(MO(o_U)){ST_AS(is_invocable_r_v);}TE  IN AbstractModule::AbstractModule(CO R& dummy,O_U o_U,GROUP M):AbstractRSet(dummy,M.One(),MO(o_U)),GROUP(MO(M)){ST_AS(is_same_v>);}TE  IN AbstractRSet& AbstractRSet::OP=(CO AbstractRSet&)NE{RE *TH;}TE  IN U RegularRSet::Action(CO U& r,U u){RE TH->Product(r,MO(u));}TE  IN U AbstractRSet::Action(CO R& r,U u){RE m_o_U(r,MO(u));}TE  IN U Module::Action(CO R& r,U u){RE MO(u *= r);}TE  IN U VirtualRSet::PW(U u,CO R& r){RE Action(r,MO(u));}TE  IN U VirtualRSet::ScalarProduct(CO R& r,U u){RE Action(r,MO(u));}

/* ConstexprModulo (7KB)*/
CEXPR(uint,P,998244353);
#define RP Represent
#define DeRP Derepresent

TE  CE INT Residue(INT n)NE{RE MO(n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n < INT(M)?n:n %= M);}TE  CE INT& ResidueP(INT& n)NE{CE CO uint trunc =(1 << 23)- 1;INT n_u = n >> 23;n &= trunc;INT n_uq =(n_u / 7)/ 17;n_u -= n_uq * 119;n += n_u << 23;RE n < n_uq?n += P - n_uq:n -= n_uq;}
TE  CL Mod;TE CL COantsForMod{PU:COantsForMod()= delete;ST CE CO uint g_memory_bound = 1e6;ST CE CO uint g_memory_LE = M < g_memory_bound?M:g_memory_bound;ST CE uint g_M_minus = M - 1;ST CE int g_order_minus_1 = M - 2;ST CE int g_order_minus_1_neg = -g_order_minus_1;};
#define SFINAE_FOR_MOD enable_if_t>>*
#define DC_OF_CM_FOR_MOD(OPR)CE bool OP OPR(CO Mod& n)CO NE
#define DC_OF_AR_FOR_MOD(OPR,EX)CE Mod OP OPR(Mod n)CO EX;
#define DF_OF_CM_FOR_MOD(OPR)TE  CE bool Mod::OP OPR(CO Mod& n)CO NE{RE m_n OPR n.m_n;}
#define DF_OF_AR_FOR_MOD(OPR,EX,LEFT,OPR2)TE  CE Mod Mod::OP OPR(Mod n)CO EX{RE MO(LEFT OPR2 ## = *TH);}TE  CE Mod OP OPR(T n0,CO Mod& n1)EX{RE MO(Mod(MO(n0))OPR ## = n1);}
TE CL Mod{PU:uint m_n;CE Mod()NE;CE Mod(CO Mod& n)NE;CE Mod(Mod&& n)NE;TE  CE Mod(T n)NE;CE Mod& OP=(Mod n)NE;CE Mod& OP+=(CO Mod& n)NE;CE Mod& OP-=(CO Mod& n)NE;CE Mod& OP*=(CO Mod& n)NE;IN Mod& OP/=(Mod n);TE  CE Mod& OP<<=(INT n);TE  CE Mod& OP>>=(INT n);CE Mod& OP++()NE;CE Mod OP++(int)NE;CE Mod& OP--()NE;CE Mod OP--(int)NE;DC_OF_CM_FOR_MOD(==);DC_OF_CM_FOR_MOD(!=);DC_OF_CM_FOR_MOD(<);DC_OF_CM_FOR_MOD(<=);DC_OF_CM_FOR_MOD(>);DC_OF_CM_FOR_MOD(>=);DC_OF_AR_FOR_MOD(+,NE);DC_OF_AR_FOR_MOD(-,NE);DC_OF_AR_FOR_MOD(*,NE);DC_OF_AR_FOR_MOD(/,);TE  CE Mod OP^(INT EX)CO;TE  CE Mod OP<<(INT n)CO;TE  CE Mod OP>>(INT n)CO;CE Mod OP-()CO NE;CE Mod& SignInvert()NE;IN Mod& Invert();TE  CE Mod& PW(INT EX);CE VO swap(Mod& n)NE;CE CRUI RP()CO NE;ST CE Mod DeRP(uint n)NE;ST IN CO Mod& Inverse(CRUI n);ST IN CO Mod& Factorial(CRUI n);ST IN CO Mod& FactorialInverse(CRUI n);ST IN Mod Combination(CRUI n,CRUI i);ST IN CO Mod& zero()NE;ST IN CO Mod& one()NE;ST IN CE uint GetModulo()NE;TE  CE Mod& PositivePW(INT EX)NE;TE  CE Mod& NonNegativePW(INT EX)NE;US COants = COantsForMod;};
US MP = Mod;
TE  CE Mod::Mod()NE:m_n(){}TE  CE Mod::Mod(CO Mod& n)NE:m_n(n.m_n){}TE  CE Mod::Mod(Mod&& n)NE:m_n(MO(n.m_n)){}TE  TE  CE Mod::Mod(T n)NE:m_n(Residue(MO(n))){}TE  CE Mod& Mod::OP=(Mod n)NE{m_n = MO(n.m_n);RE *TH;}TE  CE Mod& Mod::OP+=(CO Mod& n)NE{(m_n += n.m_n)< M?m_n:m_n -= M;RE *TH;}TE  CE Mod& Mod::OP-=(CO Mod& n)NE{m_n < n.m_n?(m_n += M)-= n.m_n:m_n -= n.m_n;RE *TH;}TE  CE Mod& Mod::OP*=(CO Mod& n)NE{m_n = MO(ull(m_n)* n.m_n)% M;RE *TH;}TE <> CE MP& MP::OP*=(CO MP& n)NE{ull m_n_copy = m_n;m_n = MO((m_n_copy *= n.m_n)< P?m_n_copy:ResidueP(m_n_copy));RE *TH;}TE  IN Mod& Mod::OP/=(Mod n){RE OP*=(n.Invert());}TE  TE  CE Mod& Mod::OP<<=(INT n){AS(n >= 0);RE *TH *= Mod(2).NonNegativePW(MO(n));}TE  TE  CE Mod& Mod::OP>>=(INT n){AS(n >=0);WH(n-- > 0){((m_n & 1)== 0?m_n:m_n += M)>>= 1;}RE *TH;}TE  CE Mod& Mod::OP++()NE{m_n < COants::g_M_minus?++m_n:m_n = 0;RE *TH;}TE  CE Mod Mod::OP++(int)NE{Mod n{*TH};OP++();RE n;}TE  CE Mod& Mod::OP--()NE{m_n == 0?m_n = COants::g_M_minus:--m_n;RE *TH;}TE  CE Mod Mod::OP--(int)NE{Mod n{*TH};OP--();RE n;}DF_OF_CM_FOR_MOD(==);DF_OF_CM_FOR_MOD(!=);DF_OF_CM_FOR_MOD(>);DF_OF_CM_FOR_MOD(>=);DF_OF_CM_FOR_MOD(<);DF_OF_CM_FOR_MOD(<=);DF_OF_AR_FOR_MOD(+,NE,n,+);DF_OF_AR_FOR_MOD(-,NE,n.SignInvert(),+);DF_OF_AR_FOR_MOD(*,NE,n,*);DF_OF_AR_FOR_MOD(/,,n.Invert(),*);TE  TE  CE Mod Mod::OP^(INT EX)CO{RE MO(Mod(*TH).PW(MO(EX)));}TE  TE  CE Mod Mod::OP<<(INT n)CO{RE MO(Mod(*TH)<<= MO(n));}TE  TE  CE Mod Mod::OP>>(INT n)CO{RE MO(Mod(*TH)>>= MO(n));}TE  CE Mod Mod::OP-()CO NE{RE MO(Mod(*TH).SignInvert());}TE  CE Mod& Mod::SignInvert()NE{m_n > 0?m_n = M - m_n:m_n;RE *TH;}TE  IN Mod& Mod::Invert(){AS(m_n != 0);uint m_n_neg;RE m_n < COants::g_memory_LE?(m_n = Inverse(m_n).m_n,*TH):((m_n_neg = M - m_n)< COants::g_memory_LE)?(m_n = M - Inverse(m_n_neg).m_n,*TH):NonNegativePW(COants::g_order_minus_1);}TE  TE  CE Mod& Mod::PositivePW(INT EX)NE{Mod PW{*TH};EX--;WH(EX != 0){(EX & 1)== 1?*TH *= PW:*TH;EX >>= 1;PW *= PW;}RE *TH;}TE  TE  CE Mod& Mod::NonNegativePW(INT EX)NE{RE EX == 0?(m_n = 1,*TH):PositivePW(MO(EX));}TE  TE  CE Mod& Mod::PW(INT EX){bool neg = EX < 0;AS(!(neg && m_n == 0));RE neg?PositivePW(ll(MO(EX %= COants::g_M_minus))* COants::g_order_minus_1_neg %COants::g_M_minus):NonNegativePW(MO(EX));}TE  CE VO Mod::swap(Mod& n)NE{std::swap(m_n,n.m_n);}TE  IN CO Mod& Mod::Inverse(CRUI n){AS(n < M);ST VE> memory ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory.push_back(DeRP(M - memory[M % LE_curr].m_n * ull(M / LE_curr)% M));LE_curr++;}RE memory[n];}TE  IN CO Mod& Mod::Factorial(CRUI n){if(M <= n){RE zero();}ST VE> memory ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory.push_back(memory[LE_curr - 1]* LE_curr);LE_curr++;}RE memory[n];}TE  IN CO Mod& Mod::FactorialInverse(CRUI n){ST VE> memory ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory.push_back(memory[LE_curr - 1]* Inverse(LE_curr));LE_curr++;}RE memory[n];}TE  IN Mod Mod::Combination(CRUI n,CRUI i){RE i <= n?Factorial(n)* FactorialInverse(i)* FactorialInverse(n - i):zero();}TE  CE CRUI Mod::RP()CO NE{RE m_n;}TE  CE Mod Mod::DeRP(uint n)NE{Mod n_copy{};n_copy.m_n = MO(n);RE n_copy;}TE  IN CO Mod& Mod::zero()NE{ST CE CO Mod z{};RE z;}TE  IN CO Mod& Mod::one()NE{ST CE CO Mod o{1};RE o;}TE  IN CE uint Mod::GetModulo()NE{RE M;}TE  IN Mod Inverse(CO Mod& n){RE MO(Mod(n).Invert());}TE  CE Mod PW(Mod n,INT EX){RE MO(n.PW(MO(EX)));}TE  CE VO swap(Mod& n0,Mod& n1)NE{n0.swap(n1);}TE  IN string to_string(CO Mod& n)NE{RE to_string(n.RP())+ " + " + to_string(M)+ "Z";}TE  IN IS& OP>>(IS& is,Mod& n){ll m;is >> m;n = m;RE is;}TE  IN OS& OP<<(OS& os,CO Mod& n){RE os << n.RP();}
#define DF_OF_HASH_FOR_MOD(MOD)IN size_t hash::OP()(CO MOD& n)CO{ST CO hash h;RE h(n.RP());}
TE  DC_OF_HASH(Mod); TE  DF_OF_HASH_FOR_MOD(Mod);

/* Loop (1KB)*/
TE  bool NextLoop(CRI SZ,CO VE& lower_bound,CO VE& upper_limit,VE& index){int depth = 0;WH(depth < SZ){if(++index[depth]< upper_limit[depth]){break;}index[depth]= lower_bound[depth];depth++;}RE depth < SZ;}TE  bool NextLoop(CO VE& lower_bound,CO VE& upper_limit,VE& index){RE NextLoop(index.SZ(),lower_bound,upper_limit,index);}TE  bool NextLoopEq(CRI SZ,CO VE& lower_bound,CO VE& upper_bound,VE& index){int depth = 0;WH(depth < SZ){if(++index[depth]<= upper_bound[depth]){break;}index[depth]= lower_bound[depth];depth++;}RE depth < SZ;}TE  bool NextLoopEq(CO VE& lower_bound,CO VE& upper_bound,VE& index){RE NextLoopEq(index.SZ(),lower_bound,upper_bound,index);}

/* string (1KB)*/
TE  IN char IntToChar(CO INT& i,CO char& c = 'a'){RE c + i;}TE  IN INT CharToInt(CO char& i){RE i -(i < 'a'?'A':'a');}TE string ArrayToString(CO VE& A,CO char& c = 'a'){CO int N = A.SZ();string S(N,c);for(int i = 0;i < N;i++){S[i]= IntToChar(A[i],c);}RE S;}TE VE StringToArray(CO string& S){CO int N = S.SZ();VE A(N);for(int i = 0;i < N;i++){A[i]= CharToInt(S[i]);}RE A;}
#endif
/* AAA 常設ライブラリは以上に挿入する。*/

#define INCLUDE_LIBRARY
#include __FILE__
#endif /* INCLUDE_LIBRARY */
#endif /* INCLUDE_SUB */
#endif /* INCLUDE_MAIN */