using H=bool;using P=void;using Q=unsigned char;using ae=long double;using ai=unsigned;using aj=char;using ar=long long;using at=__uint128_t;using ax=unsigned long long;using ay=__int128_t;
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#define dump(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(...)
#include <algorithm>
#include <any>
#include <array>
#include <atomic>
#include <barrier>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfenv>
#include <cfloat>
#include <charconv>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <clocale>
#include <cmath>
#include <codecvt>
#include <compare>
#include <complex>
#include <concepts>
#include <condition_variable>
#include <coroutine>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstring>
#include <ctime>
#include <cuchar>
#include <cwchar>
#include <cwctype>
#include <deque>
#include <exception>
#include <execution>
#include <filesystem>
#include <format>
#include <forward_list>
#include <fstream>
#include <functional>
#include <future>
#include <iomanip>
#include <initializer_list>
#include <iostream>
#include <ios>
#include <iosfwd>
#include <istream>
#include <iterator>
#include <latch>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <memory_resource>
#include <mutex>
#include <new>
#include <numbers>
#include <numeric>
#include <optional>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <semaphore>
#include <set>
#include <shared_mutex>
#include <source_location>
#include <span>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <stop_token>
#include <streambuf>
#include <string>
#include <string_view>
#include <syncstream>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <variant>
#include <vector>
template<class...T>using F=std::vector<T...>;
#include <version>
#include <sys/stat.h>
#include <unistd.h>
namespace aI{namespace eO{namespace internal{template<class T,class=P>struct gZ:std::false_type{};template<class T>struct gZ<T,std::void_t<decltype(std::begin(std::declval<T&>())),decltype(std::end(std::declval<T&>()))>>:std::true_type{};template<class T>inline constexpr H dR=gZ<T>::value;template<class T>using ii=decltype(*std::begin(std::declval<T&>()));template<class T>using ir=std::remove_cv_t<std::remove_reference_t<ii<T>>>;template<class T,class=P>struct gw{using type=ir<T>;};template<class T>struct gw<T,std::void_t<typename std::remove_cv_t<std::remove_reference_t<T>>::value_type>>{using type=typename std::remove_cv_t<std::remove_reference_t<T>>::value_type;};template<class T>using gt=typename gw<T>::type;template<class T>struct gI:std::false_type{};template<class T,std::size_t N>struct gI<T[N]>:std::bool_constant<std::is_same_v<std::remove_cv_t<T>,aj>>{};template<class T>struct im:std::bool_constant<std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,const aj*>||std::is_same_v<std::decay_t<T>,aj*>||gI<std::remove_reference_t<T>>::value>{};template<class T>inline constexpr H eD=im<T>::value;template<class T,class=P>struct gD:std::false_type{};template<class T>struct gD<T,std::void_t<decltype(std::declval<const T&>().val())>>:std::true_type{};template<class T>inline constexpr H gA=gD<T>::value;template<class T,class=P>struct gv:std::false_type{};template<class T>struct gv<T,std::void_t<decltype(T::o()),decltype(T::ct(std::declval<uint32_t>()))>>:std::true_type{};template<class T>inline constexpr H hZ=gv<T>::value;template<class T>inline constexpr H eG=std::is_integral_v<T>||std::is_same_v<std::remove_cv_t<T>,ay>||std::is_same_v<std::remove_cv_t<T>,at>;template<class T>inline constexpr H fq=std::is_signed_v<T>||std::is_same_v<std::remove_cv_t<T>,ay>;template<class T>struct fn{using type=std::make_unsigned_t<T>;};template<>struct fn<ay>{using type=at;};template<>struct fn<at>{using type=at;};template<class T>using ik=typename fn<std::remove_cv_t<T>>::type;}struct cR{static constexpr int ca=1<<20;private:std::FILE*dv;aj aD[ca];int ac;int bh;int eC;H fr;H hl(){ac=0;if(fr){ssize_t cX;do{cX=::read(eC,aD,ca);}while(cX<0&&errno==EINTR);if(cX<=0){bh=0;return false;}bh=int(cX);}else{bh=int(std::fread(aD,1,ca,dv));}return bh!=0;}template<class T>H hW(T&w){if(!eJ())return false;int c=bn();H bw=false;if(c=='-'){bw=true;c=bn();}if constexpr(internal::fq<T>){T C=0;while('0'<=c&&c<='9'){C=bw?C*10-(c-'0'):C*10+(c-'0');c=bn();}w=C;}else{T C=0;while('0'<=c&&c<='9'){C=C*10+T(c-'0');c=bn();}w=bw?T(0)-C:C;}return true;}H io(){if(bh-ac>=64)return true;const int cd=bh-ac;if(cd>0)std::memmove(aD,aD+ac,cd);const int iN=int(std::fread(aD+cd,1,ca-cd,dv));ac=0;bh=cd+iN;if(bh<ca)aD[bh]='\0';return bh!=0;}public:explicit cR(std::FILE*eU=stdin):dv(eU),ac(0),bh(0),eC(::fileno(eU)),fr([&]{struct stat hn;return eC>=0&&::fstat(eC,&hn)==0&&!S_ISREG(hn.st_mode);}()){}cR(const cR&)=delete;cR&operator=(const cR&)=delete;int bn(){if(ac==bh&&!hl())return EOF;return aD[ac++];}H eJ(){int c=bn();while(c!=EOF&&c<=' ')c=bn();if(c==EOF)return false;--ac;return true;}H read(aj&w){if(!eJ())return false;w=aj(bn());return true;}H read(std::string&w){if(!eJ())return false;w.clear();while(true){const int begin=ac;while(ac<bh&&static_cast<Q>(aD[ac])>' '){++ac;}w.append(aD+begin,ac-begin);if(ac<bh){++ac;return true;}if(!hl())return true;}}H read(H&w){int x;if(!read(x))return false;w=x!=0;return true;}template<class T>std::enable_if_t<internal::eG<T>&&!std::is_same_v<std::remove_cv_t<T>,H>&&!std::is_same_v<std::remove_cv_t<T>,aj>,H>read(T&w){if(fr)return hW(w);if(!io())return false;int c=static_cast<Q>(aD[ac++]);while(c<=' ')c=static_cast<Q>(aD[ac++]);H bw=false;if(c=='-'){bw=true;c=static_cast<Q>(aD[ac++]);}if constexpr(internal::fq<T>){T C=0;while('0'<=c&&c<='9'){const int ah=c-'0';const int ao=static_cast<Q>(aD[ac])-'0';if(0<=ao&&ao<=9){C=bw?C*100-(ah*10+ao):C*100+(ah*10+ao);++ac;}else{C=bw?C*10-ah:C*10+ah;}c=static_cast<Q>(aD[ac++]);}w=C;}else{T C=0;while('0'<=c&&c<='9'){const ai ah=ai(c-'0');const int ao=static_cast<Q>(aD[ac])-'0';if(0<=ao&&ao<=9){C=C*100+T(ah*10+ai(ao));++ac;}else{C=C*10+T(ah);}c=static_cast<Q>(aD[ac++]);}w=bw?T(0)-C:C;}if(ac>bh)ac=bh;return true;}template<class T>std::enable_if_t<std::is_floating_point_v<T>,H>read(T&w){if(!eJ())return false;int c=bn();H bw=false;if(c=='-'||c=='+'){bw=c=='-';c=bn();}ae C=0;while('0'<=c&&c<='9'){C=C*10+(c-'0');c=bn();}if(c=='.'){ae hq=0.1L;c=bn();while('0'<=c&&c<='9'){C+=(c-'0')*hq;hq*=0.1L;c=bn();}}if(c=='e'||c=='E'){c=bn();H gx=false;if(c=='-'||c=='+'){gx=c=='-';c=bn();}int au=0;while('0'<=c&&c<='9'){au=au*10+(c-'0');c=bn();}ae fP=1;ae bV=10;while(au>0){if(au&1)fP*=bV;bV*=bV;au>>=1;}C=gx?C/fP:C*fP;}w=static_cast<T>(bw?-C:C);return true;}template<class T>std::enable_if_t<internal::gA<T>&&!internal::eG<T>&&!internal::dR<T>,H>read(T&w){ar x;if(!read(x))return false;if constexpr(internal::hZ<T>){if(x>=0&&uint64_t(x)<uint64_t(T::o())){w=T::ct(uint32_t(x));}else{w=T(x);}}else{w=T(x);}return true;}template<class dy,class eo>H read(std::pair<dy,eo>&w){if(!read(w.first))return false;return read(w.second);}template<class cE>std::enable_if_t<internal::dR<cE>&&!internal::eD<cE>,H>read(cE&fO){using dp=internal::gt<cE>;constexpr H eS=internal::dR<dp>&&!internal::eD<dp>;for(auto&&w:fO){if constexpr(std::is_same_v<dp,H>&&!eS){H x;if(!read(x))return false;w=x;}else{if(!read(w))return false;}}return true;}template<class dy,class eo,class...fQ>H read(dy&ah,eo&ao,fQ&...rest){if(!read(ah))return false;return read(ao,rest...);}template<class T>cR&operator>>(T&w){if(!read(w))std::abort();return*this;}};struct cx{static constexpr int ca=1<<20;private:inline static const auto gQ=[]{std::array<aj,40000>C{};for(int i=0;i<10000;i++){int w=i;for(int j=3;j>=0;j--){C[4*i+j]=aj('0'+w%10);w/=10;}}return C;}();std::FILE*dv;aj aD[ca];int ac;int ei;std::chars_format eF;aj fj;public:explicit cx(std::FILE*eU=stdout):dv(eU),ac(0),ei(6),eF(std::chars_format::general),fj(' '){}cx(const cx&)=delete;cx&operator=(const cx&)=delete;~cx(){eV();}P eV(){if(ac!=0){std::fwrite(aD,1,ac,dv);ac=0;}std::fflush(dv);}P cb(aj c){if(ac==ca)eV();aD[ac++]=c;}P bk(const aj*s){while(*s!='\0')cb(*s++);}P bk(const std::string&s){std::size_t ce=0;while(ce<s.size()){if(ac==ca)eV();const std::size_t fF=std::min<std::size_t>(ca-ac,s.size()-ce);std::memcpy(aD+ac,s.data()+ce,fF);ac+=int(fF);ce+=fF;}}P bk(aj c){cb(c);}P bk(H w){cb(w?'1':'0');}template<class T>std::enable_if_t<std::is_floating_point_v<T>>bk(T w){aj dU[128];auto[end,iP]=std::to_chars(dU,dU+sizeof(dU),w,eF,ei);if(iP!=std::errc())std::abort();for(const aj*fE=dU;fE!=end;fE++){cb(*fE);}}template<class T>std::enable_if_t<internal::eG<T>&&!std::is_same_v<std::remove_cv_t<T>,H>&&!std::is_same_v<std::remove_cv_t<T>,aj> >bk(T w){using hv=std::remove_cv_t<T>;using el=internal::ik<hv>;el bJ;if constexpr(internal::fq<hv>){if(w<0){cb('-');bJ=el(0)-el(w);}else{bJ=el(w);}}else{bJ=w;}if(bJ==0){cb('0');return;}ai hi[16];int aV=0;while(bJ>=10000){const el em=bJ/10000;hi[aV++]=ai(bJ-em*10000);bJ=em;}if(ac>ca-64)eV();const ai eQ=ai(bJ);const aj*ah=gQ.data()+4*eQ;int fX=eQ<10?3:eQ<100?2:eQ<1000?1:0;for(;fX<4;fX++)aD[ac++]=ah[fX];while(aV--){const aj*dU=gQ.data()+4*hi[aV];std::memcpy(aD+ac,dU,4);ac+=4;}}template<class T>std::enable_if_t<internal::gA<T>&&!internal::eG<T>&&!internal::dR<T> >bk(const T&w){bk(w.val());}template<class dy,class eo>P bk(const std::pair<dy,eo>&w){bk(w.first);cb(' ');bk(w.second);}template<class cE>std::enable_if_t<internal::dR<cE>&&!internal::eD<cE> >bk(const cE&fO){using dp=internal::gt<const cE>;constexpr H eS=internal::dR<dp>&&!internal::eD<dp>;H ah=true;for(const auto&w:fO){if(!ah)cb(eS?'\n':fj);ah=false;if constexpr(std::is_same_v<dp,H>&&!eS){bk(static_cast<H>(w));}else{bk(w);}}}template<class dy,class...fQ>P fM(const dy&ah,const fQ&...rest){bk(ah);((cb(' '),bk(rest)),...);}P println(){cb('\n');}P jm(int ek){ei=ek;}P jp(int ek=6){eF=std::chars_format::fixed;ei=ek;}P jn(int ek=6){eF=std::chars_format::general;ei=ek;}P jk(aj iH){fj=iH;}template<class...Args>P println(const Args&...args){fM(args...);cb('\n');}template<class T>cx&operator<<(const T&w){bk(w);return*this;}};}}using namespace std;namespace aI{namespace cm{inline eO::cR&hp(){static eO::cR fy;return fy;}inline eO::cx&cY(){static eO::cx fy;return fy;}}}using ll=ar;using K=unsigned int;using bW=ax;using fT=__int128;using jI=unsigned __int128;
#ifdef __SIZEOF_FLOAT128__
using jH=__float128;
#endif
template<class T>constexpr T bj=0;template<>constexpr int bj<int> =1'000'000'000;template<>constexpr ll bj<ll> =ll(bj<int>)*bj<int>*2;template<>constexpr K bj<K> =bj<int>;template<>constexpr bW bj<bW> =bj<ll>;template<>constexpr fT bj<fT> =fT(bj<ll>)*bj<ll>;template<>constexpr double bj<double> =bj<ll>;template<>constexpr ae bj<ae> =bj<ll>;using pi=pair<int,int>;using pl=pair<ll,ll>;using vi=vector<int>;using vl=vector<ll>;template<class T>using vc=vector<T>;template<class T>using gf=vector<vc<T>>;using jP=gf<int>;using jQ=gf<ll>;template<class T>using iT=vector<gf<T>>;template<class T>using iS=vector<iT<T>>;template<class T>using jA=vector<iS<T>>;template<class T>using jO=std::priority_queue<T,vector<T>,greater<T>>;template<class T,class U>using jJ=unordered_map<T,U>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)     vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)             vector<vector<vector<vector<type>>>> name(         a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR1(a) for (ll _ = 0; _ < (ll)a; ++_)
#define FOR2(i, a) for (ll i = 0; i < (ll)a; ++i)
#define FOR3(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < (ll)b; i += (c))
#define FOR1_R(a) for (ll i = (a) - 1; i >= 0; --i)
#define FOR2_R(i, a) for (ll i = (a) - 1; i >= 0; --i)
#define FOR3_R(i, a, b) for (ll i = (b) - 1; i >= (ll)a; --i)
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FORI1(a) for (int _ = 0; _ < (int)a; ++_)
#define FORI2(i, a) for (int i = 0; i < (int)a; ++i)
#define FORI3(i, a, b) for (int i = a; i < (int)b; ++i)
#define FORI4(i, a, b, c) for (int i = a; i < (int)b; i += (c))
#define FORI1_R(a) for (int i = (a) - 1; i >= 0; --i)
#define FORI2_R(i, a) for (int i = (a) - 1; i >= 0; --i)
#define FORI3_R(i, a, b) for (int i = (b) - 1; i >= (int)a; --i)
#define FORI(...) overload4(__VA_ARGS__, FORI4, FORI3, FORI2, FORI1)(__VA_ARGS__)
#define FORI_R(...) overload3(__VA_ARGS__, FORI3_R, FORI2_R, FORI1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (int t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
int fI(int x){return __builtin_popcount(x);}int fI(K x){return __builtin_popcount(x);}int fI(ll x){return __builtin_popcountll(x);}int fI(bW x){return __builtin_popcountll(x);}int fp(int x){return __builtin_parity(x);}int fp(K x){return __builtin_parity(x);}int fp(ll x){return __builtin_parityll(x);}int fp(bW x){return __builtin_parityll(x);}int fJ(int x){return(x==0?-1:31-__builtin_clz(x));}int fJ(K x){return(x==0?-1:31-__builtin_clz(x));}int fJ(ll x){return(x==0?-1:63-__builtin_clzll(x));}int fJ(bW x){return(x==0?-1:63-__builtin_clzll(x));}int fH(int x){return(x==0?-1:__builtin_ctz(x));}int fH(K x){return(x==0?-1:__builtin_ctz(x));}int fH(ll x){return(x==0?-1:__builtin_ctzll(x));}int fH(bW x){return(x==0?-1:__builtin_ctzll(x));}template<typename T>T fL(T a,T b){return a/b-(a%b&&(a^b)<0);}template<typename T>T jF(T x,T y){return fL(x+y-1,y);}template<typename T>T jE(T x,T y){return x-y*fL(x,y);}template<typename T>pair<T,T>jx(T x,T y){T q=fL(x,y);return{q,x-q*y};}template<typename T,typename U>T jK(U x_,int n){T x=x_;T hE=1;while(n>0){if(n&1)hE*=x;x*=x;n>>=1;}return hE;}template<typename T,typename U>T jL(const vector<U>&A){T sm=0;for(auto&&a:A)sm+=a;return sm;}
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template<class T,class S>inline H jD(T&a,const S&b){return(a<b?a=b,1:0);}template<class T,class S>inline H iO(T&a,const S&b){return(a>b?a=b,1:0);}vc<int>ju(const string&S,aj iB){vc<int>A(S.size());FOR(i,S.size()){A[i]=(S[i]!='?'?S[i]-iB:-1);}return A;}template<typename T,typename U>vector<T>jw(vector<U>&A,int iY=1){int N=A.size();vector<T>B(N+1);FOR(i,N){B[i+1]=B[i]+A[i];}if(iY==0)B.erase(B.begin());return B;}template<typename T>vector<int>jr(const vector<T>&A){vector<int>fZ(A.size());iota(all(fZ),0);sort(all(fZ),[&](int i,int j){return(A[i]==A[j]?i<j:A[i]<A[j]);});return fZ;}template<typename T>vc<T>jo(const vc<T>&A,const vc<int>&I){vc<T>B(I.size());FOR(i,I.size())B[i]=A[I[i]];return B;}template<class...T>constexpr auto iW(T...a){return iW(initializer_list<common_type_t<T...>>{a...});}template<class...T>constexpr auto iV(T...a){return iV(initializer_list<common_type_t<T...>>{a...});}template<class...Ts>H fW(Ts&...aq){return aI::cm::hp().read(aq...);}template<class...Ts>P fM(const Ts&...aq){aI::cm::cY().println(aq...);}P jB(H b){aI::cm::cY().println(b?"YES":"NO");}P jC(H b){aI::cm::cY().println(b?"Yes":"No");}P jM(){aI::cm::cY().println("YES");}P NO(){aI::cm::cY().println("NO");}P jN(){aI::cm::cY().println("Yes");}P No(){aI::cm::cY().println("No");}auto&jy=aI::cm::hp();auto&js=aI::cm::cY();namespace aI{namespace ci{template<uint32_t bg>struct R{static_assert(0<bg,"Modulus must be positive");private:uint32_t J;public:static constexpr uint32_t o(){return bg;}static constexpr R ct(uint32_t v)noexcept{R x;x.J=v;return x;}constexpr R()noexcept:J(0){}template<class du,std::enable_if_t<std::is_integral_v<du>,int> =0>constexpr R(du v)noexcept{if constexpr(std::is_signed_v<du>){int64_t x=static_cast<int64_t>(v)%static_cast<int64_t>(bg);if(x<0)x+=bg;J=static_cast<uint32_t>(x);}else{J=static_cast<uint32_t>(static_cast<uint64_t>(v)%bg);}}constexpr uint32_t val()const noexcept{return J;}constexpr R&operator++()noexcept{J++;if(J==bg)J=0;return*this;}constexpr R&operator--()noexcept{if(J==0)J=bg;J--;return*this;}constexpr R operator++(int)noexcept{R eb=*this;++*this;return eb;}constexpr R operator--(int)noexcept{R eb=*this;--*this;return eb;}constexpr R&operator+=(const R&O)noexcept{J+=O.J;if(J>=bg)J-=bg;return*this;}constexpr R&operator-=(const R&O)noexcept{J-=O.J;if(J>=bg)J+=bg;return*this;}constexpr R&operator*=(const R&O)noexcept{uint64_t z=J;z*=O.J;J=static_cast<uint32_t>(z%bg);return*this;}constexpr R&operator/=(const R&O)noexcept{return*this*=O.inv();}constexpr R operator+(const R&O)const noexcept{return R(*this)+=O;}constexpr R operator-(const R&O)const noexcept{return R(*this)-=O;}constexpr R operator*(const R&O)const noexcept{return R(*this)*=O;}constexpr R operator/(const R&O)const noexcept{return R(*this)/=O;}constexpr H operator==(const R&O)const noexcept{return J==O.J;}constexpr H operator!=(const R&O)const noexcept{return J!=O.J;}constexpr R pow(ar n)const noexcept{R eb=ct(1%bg);R x=n<0?inv():*this;uint64_t au=n<0?uint64_t(-(n+1))+1:uint64_t(n);while(au>0){if(au&1)eb*=x;x*=x;au>>=1;}return eb;}constexpr R inv()const noexcept{int64_t a=J,b=bg,u=1,v=0;while(b){int64_t t=a/b;a-=t*b;std::swap(a,b);u-=t*v;std::swap(u,v);}assert(a==1);u%=bg;if(u<0)u+=bg;return ct(static_cast<uint32_t>(u));}friend std::ostream&operator<<(std::ostream&os,const R&O){return os<<O.J;}friend std::istream&operator>>(std::istream&is,R&O){ar v;is>>v;O=R(v);return is;}};using il=R<998244353>;using jl=R<1000000007>;template<int Id=0>struct ag{private:uint32_t J;inline static uint32_t ba=1;public:static uint32_t o()noexcept{return ba;}static P jv(uint32_t cC)noexcept{assert(cC>0);assert(cC<=uint32_t(1)<<31);ba=cC;}static ag ct(uint32_t v)noexcept{assert(v<ba);ag x;x.J=v;return x;}ag()noexcept:J(0){}template<class du,std::enable_if_t<std::is_integral_v<du>,int> =0>ag(du v)noexcept{if constexpr(std::is_signed_v<du>){int64_t x=static_cast<int64_t>(v)%static_cast<int64_t>(ba);if(x<0)x+=ba;J=static_cast<uint32_t>(x);}else{J=static_cast<uint32_t>(static_cast<uint64_t>(v)%ba);}}uint32_t val()const noexcept{return J;}ag&operator++()noexcept{J++;if(J==ba)J=0;return*this;}ag&operator--()noexcept{if(J==0)J=ba;J--;return*this;}ag operator++(int)noexcept{ag C=*this;++*this;return C;}ag operator--(int)noexcept{ag C=*this;--*this;return C;}ag&operator+=(const ag&O)noexcept{J+=O.J;if(J>=ba)J-=ba;return*this;}ag&operator-=(const ag&O)noexcept{J-=O.J;if(J>=ba)J+=ba;return*this;}ag&operator*=(const ag&O)noexcept{J=static_cast<uint32_t>(uint64_t(J)*O.J%ba);return*this;}ag&operator/=(const ag&O)noexcept{return*this*=O.inv();}ag operator+(const ag&O)const noexcept{return ag(*this)+=O;}ag operator-(const ag&O)const noexcept{return ag(*this)-=O;}ag operator*(const ag&O)const noexcept{return ag(*this)*=O;}ag operator/(const ag&O)const noexcept{return ag(*this)/=O;}H operator==(const ag&O)const noexcept{return J==O.J;}H operator!=(const ag&O)const noexcept{return J!=O.J;}ag pow(ar au)const noexcept{ag C=ct(1%ba);ag aW=au<0?inv():*this;uint64_t bJ=au<0?uint64_t(-(au+1))+1:uint64_t(au);while(bJ>0){if(bJ&1)C*=aW;aW*=aW;bJ>>=1;}return C;}ag inv()const noexcept{int64_t a=J,b=ba,u=1,v=0;while(b){int64_t em=a/b;a-=em*b;std::swap(a,b);u-=em*v;std::swap(u,v);}assert(a==1);u%=ba;if(u<0)u+=ba;return ct(static_cast<uint32_t>(u));}friend std::ostream&operator<<(std::ostream&os,const ag&O){return os<<O.J;}friend std::istream&operator>>(std::istream&is,ag&O){ar w;is>>w;O=ag(w);return is;}};}}
#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#include <immintrin.h>
#define M1UNE_FPS_HAS_X86_SIMD 1
#pragma GCC push_options
#pragma GCC target("avx2,bmi")
#endif
#ifdef M1UNE_FPS_HAS_X86_SIMD
#include <algorithm>
#include <array>
#include <cstdint>
#include <immintrin.h>
namespace aI{namespace cH{namespace internal{namespace cy{using K=ai;using bW=ax;using ap=std::size_t;using D=__m256i;inline P af(P*p,D x){_mm256_store_si256((D*)p,x);}inline D W(const P*p){return _mm256_load_si256((const D*)p);}constexpr K dY(K x,K M){return std::min(x,x-M);}constexpr K jG(K x,K M){return std::min(x,x+M);}constexpr K dV(bW x,K E,K M){return(x+bW(K(x)*E)*M)>>32;}constexpr K bO(K x,K y,K E,K M){return dV(bW(x)*y,E,M);}constexpr K aJ(K x,K y,K E,K M){return dY(dV(bW(x)*y,E,M),M);}constexpr K gd(K a,K b,K E,K M,K r){for(;b;b>>=1,a=bO(a,a,E,M)){if(b&1){r=bO(r,a,E,M);}}return r;}constexpr K hs(K a,K b,K E,K M,K r){return dY(gd(a,b,E,M,r),M);}inline D aN(D x,D M){return _mm256_min_epu32(x,_mm256_sub_epi32(x,M));}inline D iL(D x,D M){return _mm256_min_epu32(x,_mm256_add_epi32(x,M));}inline D cf(D x,D y,D){return _mm256_add_epi32(x,y);}inline D bi(D x,D y,D M){return _mm256_add_epi32(_mm256_sub_epi32(x,y),M);}inline D aH(D x,D y,D M){return aN(_mm256_add_epi32(x,y),M);}inline D by(D x,D y,D M){return iL(_mm256_sub_epi32(x,y),M);}template<int iX>inline D jt(D x,D M){return _mm256_blend_epi32(x,_mm256_sub_epi32(M,x),iX);}inline D dV(D a,D b,D E,D M){D c=_mm256_mul_epu32(a,E),d=_mm256_mul_epu32(b,E);c=_mm256_mul_epu32(c,M),d=_mm256_mul_epu32(d,M);return _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(a,c),32),_mm256_add_epi64(b,d),0xaa);}inline D bO(D a,D b,D E,D M){return dV(_mm256_mul_epu32(a,b),_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(b,32)),E,M);}inline D aJ(D a,D b,D E,D M){return aN(bO(a,b,E,M),M);}inline D cV(D a,D b,D E,D M){return dV(_mm256_mul_epu32(a,b),_mm256_mul_epu32(_mm256_srli_epi64(a,32),b),E,M);}inline D bI(D a,D b,D ep,D M){D cc=_mm256_mul_epu32(a,ep),dd=_mm256_mul_epu32(_mm256_srli_epi64(a,32),ep);D c=_mm256_mul_epu32(a,b),d=_mm256_mul_epu32(_mm256_srli_epi64(a,32),b);cc=_mm256_mul_epu32(cc,M),dd=_mm256_mul_epu32(dd,M);return _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),_mm256_add_epi64(d,dd),0xaa);}inline D jq(D a,D b,D ep,D M){D cc=_mm256_mul_epu32(a,ep),dd=_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(ep,32));D c=_mm256_mul_epu32(a,b),d=_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(b,32));cc=_mm256_mul_epu32(cc,M),dd=_mm256_mul_epu32(dd,M);return _mm256_blend_epi32(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),_mm256_add_epi64(d,dd),0xaa);}inline D eL(D a,D bu,D M){D cc=_mm256_mul_epu32(a,bu),c=_mm256_mul_epu32(a,_mm256_srli_epi64(bu,32));cc=_mm256_mul_epu32(cc,M);return aN(_mm256_srli_epi64(_mm256_add_epi64(c,cc),32),M);}constexpr auto bU=26,dr=6;constexpr auto cZ=ap(1)<<dr;static_assert(dr%2==0);struct dn{K o,cq,E,am,r2,r3,cs,eR,dD[bU];alignas(32)std::array<K,8>eY[bU-2],eX[bU-2],fS,fY,fR,et[bU-3],hm[bU-3],er[bU-3],he[bU-3],gb,gc,hj,hk,fU,hc,fV,hd;constexpr dn(const K m):o(m),cq(m*2),E([&]{K n=2+m;for(int i=0;i<4;++i){n*=2+m*n;}return n;}()),am((-m)%m),r2((-bW(m))%m),r3(aJ(r2,r2,E,m)),cs{},eR{},dD{},eY{},eX{},fS{},fY{},fR{},et{},hm{},er{},he{},gb{},gc{},hj{},hk{},fU{},hc{},fV{},hd{}{const int k=__builtin_ctz(m-1);K _g=bO(3,r2,E,o);for(;;++_g){if(hs(_g,o>>1,E,o,am)!=am){break;}}_g=gd(_g,o>>k,E,o,am);K bq[bU-1],bl[bU-1];bq[k-2]=_g,bl[k-2]=gd(_g,o-2,E,o,am);for(int i=k-2;i>0;--i){bq[i-1]=bO(bq[i],bq[i],E,o);bl[i-1]=bO(bl[i],bl[i],E,o);}dD[k-1]=hs(_g,3,E,o,am);for(int i=k-1;i>0;--i){dD[i-1]=aJ(dD[i],dD[i],E,o);}cs=bq[0],eR=cs*E;fS={am,0,am,0,am};fY={bq[1],0,bq[0],0,o-aJ(bq[0],bq[1],E,o)};fR={bl[1],0,bl[0],0,aJ(bl[0],bl[1],E,o)};K pr=am,dE=am;for(int i=0;i<k-2;++i){const K r=aJ(pr,bq[i+1],E,o),ri=aJ(dE,bl[i+1],E,o);const K r2=aJ(r,r,E,o),ge=aJ(ri,ri,E,o);const K r3=aJ(r,r2,E,o),hD=aJ(ri,ge,E,o);eY[i]={r*E,r,r2*E,r2,r3*E,r3};eX[i]={ri*E,ri,ge*E,ge,hD*E,hD};pr=bO(pr,bl[i+1],E,o),dE=bO(dE,bq[i+1],E,o);}pr=am,dE=am;for(int i=0;i<k-3;++i){const K r=aJ(pr,bq[i+2],E,o),ri=aJ(dE,bl[i+2],E,o);et[i][0]=er[i][0]=am;for(int j=1;j<8;++j){et[i][j]=aJ(et[i][j-1],r,E,o);er[i][j]=aJ(er[i][j-1],ri,E,o);}for(int j=0;j<8;++j){hm[i][j]=et[i][j]*E;he[i][j]=er[i][j]*E;}pr=bO(pr,bl[i+2],E,o),dE=bO(dE,bq[i+2],E,o);}gb={am,am,am,cs,am,am,am,cs};gc={am,am,am,am,am,bq[1],cs,aJ(cs,bq[1],E,o)};const K ea=o-r2,ho=aJ(cs,r2,E,o);fU={ea,ea,ea,ho,ea,ea,ea,ho};fV={am,am,am,am,am,bl[1],bl[0],aJ(bl[0],bl[1],E,o)};for(int j=0;j<8;++j){hj[j]=gb[j]*E,hk[j]=gc[j]*E;hc[j]=fU[j]*E,hd[j]=fV[j]*E;}}};inline P fv(D*const f,const ap n,const dn*al){alignas(32)std::array<K,8>bp[bU>>1];const D ad=_mm256_set1_epi32(al->o),G=_mm256_set1_epi32(al->cq),bc=_mm256_set1_epi32(al->E);const D df=_mm256_set1_epi32(al->cs),cW=_mm256_set1_epi32(al->eR),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);const int dZ=__builtin_ctzll(n);std::fill(bp,bp+(dZ>>1),al->fY);const ap nn=n>>(dZ&1),m=std::min(n,cZ),mm=std::min(nn,cZ);if(nn!=n){for(ap i=0;i<nn;++i){auto const p0=f+i,p1=f+nn+i;const auto f0=W(p0),f1=W(p1);const auto g0=aH(f0,f1,G),g1=bi(f0,f1,G);af(p0,g0),af(p1,g1);}}for(ap L=nn>>2;L>0;L>>=2){for(ap i=0;i<L;++i){auto const p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;const auto f1=W(p1),f3=W(p3),f2=W(p2),f0=W(p0);const auto g3=bI(bi(f1,f3,G),df,cW,ad),g1=aH(f1,f3,G);const auto g0=aH(f0,f2,G),g2=by(f0,f2,G);const auto h0=aH(g0,g1,G),h1=bi(g0,g1,G);const auto h2=cf(g2,g3,G),h3=bi(g2,g3,G);af(p0,h0),af(p1,h1),af(p2,h2),af(p3,h3);}}for(ap j=0;j<n;j+=m){int t=((j==0)?std::min(dr,dZ):__builtin_ctzll(j))&-2,p=(t-2)>>1;for(ap L=(ap(1)<<t)>>2;L>=cZ;L>>=2,t-=2,--p){auto rt=W(bp+p);const auto r1=_mm256_permutevar8x32_epi32(rt,id);const auto dA=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bc),id);rt=eL(rt,W(al->eY+__builtin_ctzll(~j>>t)),ad);const auto r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),ga=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);const auto fN=_mm256_shuffle_epi32(dA,_MM_PERM_BBBB),iM=_mm256_shuffle_epi32(dA,_MM_PERM_DDDD);af(bp+p,rt);for(ap i=0;i<L;++i){auto const p0=f+i+j,p1=p0+L,p2=p1+L,p3=p2+L;const auto f1=W(p1),f3=W(p3),f2=W(p2),f0=W(p0);const auto g1=bI(f1,r1,dA,ad),es=bI(f3,ga,iM,ad);const auto g2=bI(f2,r2,fN,ad),g0=aN(f0,G);const auto h3=bI(cf(g1,es,G),df,cW,ad),h1=by(g1,es,G);const auto h0=aH(g0,g2,G),h2=by(g0,g2,G);const auto u0=cf(h0,h1,G),u1=bi(h0,h1,G);const auto u2=cf(h2,h3,G),u3=bi(h2,h3,G);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}}D*const g=f+j;for(ap l=mm,L=mm>>2;L;l=L,L>>=2,t-=2,--p){auto rt=W(bp+p);for(ap i=(j==0?l:0),k=(j+i)>>t;i<m;i+=l,++k){const auto r1=_mm256_permutevar8x32_epi32(rt,id);const auto r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB);const auto ga=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);for(ap j=0;j<L;++j){auto const p0=g+i+j,p1=p0+L,p2=p1+L,p3=p2+L;const auto f1=W(p1),f3=W(p3),f2=W(p2),f0=W(p0);const auto g1=cV(f1,r1,bc,ad),es=cV(f3,ga,bc,ad);const auto g2=cV(f2,r2,bc,ad),g0=aN(f0,G);const auto h3=bI(cf(g1,es,G),df,cW,ad),h1=by(g1,es,G);const auto h0=aH(g0,g2,G),h2=by(g0,g2,G);const auto u0=cf(h0,h1,G),u1=bi(h0,h1,G);const auto u2=cf(h2,h3,G),u3=bi(h2,h3,G);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}rt=eL(rt,W(al->eY+__builtin_ctzll(~k)),ad);}af(bp+p,rt);}}}template<H dY=false>inline P gU(D*const f,ap n,const dn*const al){alignas(32)std::array<K,8>bp[bU>>1];const D ad=_mm256_set1_epi32(al->o),G=_mm256_set1_epi32(al->cq),bc=_mm256_set1_epi32(al->E);const D df=_mm256_set1_epi32(al->cs),cW=_mm256_set1_epi32(al->eR),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);const int dZ=__builtin_ctzll(n);std::fill(bp,bp+(dr>>1),al->fS);std::fill(bp+(dr>>1),bp+(bU>>1),al->fR);const ap nn=n>>(dZ&1),mm=std::min(nn,cZ);for(ap j=0;j<n;j+=mm){D*const g=f+j;int t=2,p=0;for(ap l=4,L=1;l<=mm;L=l,l<<=2,t+=2,++p){auto rt=W(bp+p);for(ap i=0,k=j>>t;i<mm;i+=l,++k){const auto r1=_mm256_permutevar8x32_epi32(rt,id);const auto r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB);const auto r3=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);for(ap j=0;j<L;++j){auto const p0=g+i+j,p1=p0+L,p2=p1+L,p3=p2+L;const auto f0=W(p0),f1=W(p1),f2=W(p2),f3=W(p3);const auto g0=aH(f0,f1,G),g1=by(f0,f1,G);const auto g2=aH(f2,f3,G),g3=bI(bi(f3,f2,G),df,cW,ad);const auto h0=cf(g0,g2,G),h1=cf(g1,g3,G);const auto h2=bi(g0,g2,G),h3=bi(g1,g3,G);const auto u0=aN(h0,G),u1=cV(h1,r1,bc,ad);const auto u2=cV(h2,r2,bc,ad),u3=cV(h3,r3,bc,ad);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}rt=eL(rt,W(al->eX+__builtin_ctzll(~k)),ad);}af(bp+p,rt);}int tt=std::min(__builtin_ctzll(~(j>>dr))+dr,dZ);for(ap L=cZ,l=L<<2;t<=tt;L=l,l<<=2,t+=2,++p){if((j+cZ)==l){if(dY&&l==n){for(ap i=0;i<L;++i){auto const p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;const auto f2=W(p2),f3=W(p3),f0=W(p0),f1=W(p1);const auto g3=bI(bi(f3,f2,G),df,cW,ad),g2=aH(f2,f3,G);const auto g0=aH(f0,f1,G),g1=by(f0,f1,G);const auto h0=aH(g0,g2,G),h1=aH(g1,g3,G);const auto h2=by(g0,g2,G),h3=by(g1,g3,G);const auto u0=aN(h0,ad),u1=aN(h1,ad);const auto u2=aN(h2,ad),u3=aN(h3,ad);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}}else{for(ap i=0;i<L;++i){auto const p0=f+i,p1=p0+L,p2=p1+L,p3=p2+L;const auto f2=W(p2),f3=W(p3),f0=W(p0),f1=W(p1);const auto g3=bI(bi(f3,f2,G),df,cW,ad),g2=aH(f2,f3,G);const auto g0=aH(f0,f1,G),g1=by(f0,f1,G);const auto h0=aH(g0,g2,G),h1=aH(g1,g3,G);const auto h2=by(g0,g2,G),h3=by(g1,g3,G);af(p0,h0),af(p1,h1),af(p2,h2),af(p3,h3);}}}else{auto rt=W(bp+p);const auto r1=_mm256_permutevar8x32_epi32(rt,id);const auto dA=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bc),id);rt=eL(rt,W(al->eX+__builtin_ctzll(~j>>t)),ad);const auto r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),r3=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);const auto fN=_mm256_shuffle_epi32(dA,_MM_PERM_BBBB),iQ=_mm256_shuffle_epi32(dA,_MM_PERM_DDDD);af(bp+p,rt);for(ap i=0;i<L;++i){auto const p0=f+j+cZ-l+i,p1=p0+L,p2=p1+L,p3=p2+L;const auto f0=W(p0),f1=W(p1),f2=W(p2),f3=W(p3);const auto g0=aH(f0,f1,G),g1=by(f0,f1,G);const auto g2=aH(f2,f3,G),g3=bI(bi(f3,f2,G),df,cW,ad);const auto h0=cf(g0,g2,G),h1=cf(g1,g3,G);const auto h2=bi(g0,g2,G),h3=bi(g1,g3,G);const auto u0=aN(h0,G),u1=bI(h1,r1,dA,ad);const auto u2=bI(h2,r2,fN,ad),u3=bI(h3,r3,iQ,ad);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}}}}if(dY&&nn==n&&n<=cZ){for(ap i=0;i<n;++i){const auto f0=W(f+i);af(f+i,aN(f0,ad));}}if(nn!=n){for(ap i=0;i<nn;++i){auto const p0=f+i,p1=f+nn+i;const auto f0=W(p0),f1=W(p1);const auto g0=aH(f0,f1,G),g1=by(f0,f1,G);if constexpr(dY){const auto h0=aN(g0,ad),h1=aN(g1,ad);af(p0,h0),af(p1,h1);}else{af(p0,g0),af(p1,g1);}}}}[[gnu::always_inline]]inline D gW(const D*f,const D*g,D ww,D fx,D bc,D ad,D G){const auto iZ=W(f),ja=W(g);const auto hG=aN(iZ,G),bb=aN(cV(ja,fx,bc,ad),ad);const auto aw=aN(cV(hG,ww,bc,ad),ad);const auto aa=aN(hG,ad);const auto dg=_mm256_permute2x128_si256(aa,aw,3);const auto b0=_mm256_permute4x64_epi64(bb,0x00),b1=_mm256_shuffle_epi32(b0,_MM_PERM_CDAB);const auto a0=aa,a1=_mm256_srli_epi64(a0,32);const auto hB=_mm256_alignr_epi8(aa,dg,12);auto cF=_mm256_mul_epu32(a0,b0);auto cG=_mm256_mul_epu32(a1,b0);auto dB=_mm256_mul_epu32(hB,b1);auto dC=_mm256_mul_epu32(a0,b1);const auto b2=_mm256_permute4x64_epi64(bb,0x55),b3=_mm256_shuffle_epi32(b2,_MM_PERM_CDAB);const auto hA=_mm256_alignr_epi8(aa,dg,8);const auto hz=_mm256_alignr_epi8(aa,dg,4);cF=_mm256_add_epi64(cF,_mm256_mul_epu32(hA,b2));cG=_mm256_add_epi64(cG,_mm256_mul_epu32(hB,b2));dB=_mm256_add_epi64(dB,_mm256_mul_epu32(hz,b3));dC=_mm256_add_epi64(dC,_mm256_mul_epu32(hA,b3));const auto b4=_mm256_permute4x64_epi64(bb,0xaa),b5=_mm256_shuffle_epi32(b4,_MM_PERM_CDAB);const auto hy=_mm256_alignr_epi8(dg,aw,12);cF=_mm256_add_epi64(cF,_mm256_mul_epu32(dg,b4));cG=_mm256_add_epi64(cG,_mm256_mul_epu32(hz,b4));dB=_mm256_add_epi64(dB,_mm256_mul_epu32(hy,b5));dC=_mm256_add_epi64(dC,_mm256_mul_epu32(dg,b5));const auto b6=_mm256_permute4x64_epi64(bb,0xff),b7=_mm256_shuffle_epi32(b6,_MM_PERM_CDAB);const auto hx=_mm256_alignr_epi8(dg,aw,8);const auto iU=_mm256_alignr_epi8(dg,aw,4);cF=_mm256_add_epi64(cF,_mm256_mul_epu32(hx,b6));cG=_mm256_add_epi64(cG,_mm256_mul_epu32(hy,b6));dB=_mm256_add_epi64(dB,_mm256_mul_epu32(iU,b7));dC=_mm256_add_epi64(dC,_mm256_mul_epu32(hx,b7));cF=_mm256_add_epi64(cF,dB);cG=_mm256_add_epi64(cG,dC);return aN(dV(cF,cG,bc,ad),G);}inline P hU(D*f,const D*g,ap lm,const dn*const al){K RR=al->am;const auto o=al->o,E=al->E;const auto Fx=_mm256_set1_epi32(aJ((o-((o-1)>>(__builtin_ctzll(lm)))),al->r3,E,o));const auto bc=_mm256_set1_epi32(E),ad=_mm256_set1_epi32(o),G=_mm256_set1_epi32(al->cq);for(ap i=0;i<lm;++i){af(f+i,gW(f+i,g+i,_mm256_set1_epi32(RR),Fx,bc,ad,G));RR=bO(RR,al->dD[__builtin_ctzll(~i)],E,o);}}inline P hS(D*const C,const D*const f,const D*const g,ap lm,const dn*const al){K RR=al->am;const auto o=al->o,E=al->E;const auto Fx=_mm256_set1_epi32(aJ((o-((o-1)>>(__builtin_ctzll(lm)))),al->r3,E,o));const auto bc=_mm256_set1_epi32(E),ad=_mm256_set1_epi32(o),G=_mm256_set1_epi32(al->cq);for(ap i=0;i<lm;++i){const auto bL=gW(f+i,g+i,_mm256_set1_epi32(RR),Fx,bc,ad,G);af(C+i,aH(W(C+i),bL,G));RR=bO(RR,al->dD[__builtin_ctzll(~i)],E,o);}}}}}}
#endif
#ifdef M1UNE_FPS_HAS_X86_SIMD
#pragma GCC pop_options
#endif
namespace aI{namespace cH{namespace internal{template<class e,class=P>struct eA:std::false_type{};template<class e>struct eA<e,std::void_t<decltype(std::integral_constant<uint32_t,e::o()>{})>>:std::true_type{};constexpr uint32_t hV(uint32_t o){if(o==2)return 1;if(o==167772161)return 3;if(o==469762049)return 3;if(o==754974721)return 11;if(o==998244353)return 3;if(o==1224736769)return 3;uint32_t eP[32]={};int aV=0;uint32_t x=o-1;for(uint32_t p=2;uint64_t(p)*p<=x;p++){if(x%p!=0)continue;eP[aV++]=p;while(x%p==0)x/=p;}if(x>1)eP[aV++]=x;for(uint32_t g=2;;g++){H ok=true;for(int i=0;i<aV;i++){uint64_t w=1;uint64_t aW=g;uint32_t au=(o-1)/eP[i];while(au>0){if(au&1)w=w*aW%o;aW=aW*aW%o;au>>=1;}if(w==1){ok=false;break;}}if(ok)return g;}}constexpr int gF(uint32_t x){int C=0;while((x&1)==0){x>>=1;C++;}return C;}template<class e>struct fw{static constexpr int cA=gF(e::o()-1);std::array<e,cA+1>cr;std::array<e,cA+1>cO;std::array<e,cA>hu;std::array<e,cA>gK;std::array<e,cA>gT;std::array<e,cA>gu;fw(){constexpr uint32_t fl=hV(e::o());for(int bx=1;bx<=cA;bx++){cr[bx]=e(fl).pow((e::o()-1)>>bx);cO[bx]=cr[bx].inv();}e bL=1;e ee=1;for(int i=0;i+1<cA;i++){hu[i]=cr[i+2]*bL;gK[i]=cO[i+2]*ee;bL*=cO[i+2];ee*=cr[i+2];}bL=1;ee=1;for(int i=0;i+2<cA;i++){gT[i]=cr[i+3]*bL;gu[i]=cO[i+3]*ee;bL*=cO[i+3];ee*=cr[i+3];}}};template<class e>const fw<e>&iG(){static const fw<e>de;return de;}template<class e>P cI(F<e>&a,H fD,H iF=true){const int n=int(a.size());assert(n>0&&(n&(n-1))==0);assert((e::o()-1)%uint32_t(n)==0);const auto&de=iG<e>();const int cg=gF(uint32_t(n));if(!fD){int av=0;while(av<cg){if(cg-av==1){const int aC=1<<(cg-av-1);e aZ=1;for(int V=0;V<(1<<av);V++){const int ab=V<<(cg-av);for(int i=0;i<aC;i++){const e cp=a[ab+i];const e co=a[ab+i+aC]*aZ;a[ab+i]=cp+co;a[ab+i+aC]=cp-co;}if(V+1!=(1<<av))aZ*=de.hu[__builtin_ctz(~uint32_t(V))];}av++;continue;}const int aC=1<<(cg-av-2);e aZ=1;const e iE=de.cr[2];for(int V=0;V<(1<<av);V++){const e en=aZ*aZ;const e fz=en*aZ;const int ab=V<<(cg-av);for(int i=0;i<aC;i++){const uint64_t cq=uint64_t(e::o())*e::o();const uint64_t a0=a[ab+i].val();const uint64_t a1=uint64_t(a[ab+i+aC].val())*aZ.val();const uint64_t a2=uint64_t(a[ab+i+2*aC].val())*en.val();const uint64_t a3=uint64_t(a[ab+i+3*aC].val())*fz.val();const uint64_t hg=uint64_t(e(a1+cq-a3).val())*iE.val();const uint64_t gS=cq-a2;a[ab+i]=e(a0+a2+a1+a3);a[ab+i+aC]=e(a0+a2+2*cq-a1-a3);a[ab+i+2*aC]=e(a0+gS+hg);a[ab+i+3*aC]=e(a0+gS+cq-hg);}if(V+1!=(1<<av))aZ*=de.gT[__builtin_ctz(~uint32_t(V))];}av+=2;}}else{int av=cg;while(av>0){if(av==1){const int aC=1<<(cg-av);e aZ=1;for(int V=0;V<(1<<(av-1));V++){const int ab=V<<(cg-av+1);for(int i=0;i<aC;i++){const e cp=a[ab+i];const e co=a[ab+i+aC];a[ab+i]=cp+co;a[ab+i+aC]=(cp-co)*aZ;}if(V+1!=(1<<(av-1)))aZ*=de.gK[__builtin_ctz(~uint32_t(V))];}av--;continue;}const int aC=1<<(cg-av);e aZ=1;const e ig=de.cO[2];for(int V=0;V<(1<<(av-2));V++){const e en=aZ*aZ;const e fz=en*aZ;const int ab=V<<(cg-av+2);for(int i=0;i<aC;i++){const uint64_t a0=a[ab+i].val();const uint64_t a1=a[ab+i+aC].val();const uint64_t a2=a[ab+i+2*aC].val();const uint64_t a3=a[ab+i+3*aC].val();const uint64_t hh=uint64_t(e((e::o()+a2-a3)*ig.val()).val());a[ab+i]=e(a0+a1+a2+a3);a[ab+i+aC]=e((a0+e::o()-a1+hh)*aZ.val());a[ab+i+2*aC]=e((a0+a1+2ULL*e::o()-a2-a3)*en.val());a[ab+i+3*aC]=e((a0+e::o()-a1+e::o()-hh)*fz.val());}if(V+1!=(1<<(av-2)))aZ*=de.gu[__builtin_ctz(~uint32_t(V))];}av-=2;}if(iF){const e eN=e(n).inv();for(e&w:a)w*=eN;}}}
#ifdef M1UNE_FPS_HAS_X86_SIMD
#pragma GCC push_options
#pragma GCC target("avx2,bmi")
template<class e>__attribute__((target("avx2,bmi"),hot))F<e>hT(const F<e>&a,const F<e>&b){const int bf=int(a.size()+b.size()-1);int n=1;while(n<bf)n<<=1;const H cU=&a==&b;auto*bH=static_cast<uint32_t*>(::operator new[](sizeof(uint32_t)*n,std::align_val_t(32)));auto*cl=cU?bH:static_cast<uint32_t*>(::operator new[](sizeof(uint32_t)*n,std::align_val_t(32)));if constexpr(std::is_same_v<e,ci::R<998244353>>){static_assert(sizeof(e)==sizeof(uint32_t)&&std::is_trivially_copyable_v<e>);std::memcpy(bH,a.data(),sizeof(uint32_t)*a.size());if(!cU)std::memcpy(cl,b.data(),sizeof(uint32_t)*b.size());}else{for(int i=0;i<int(a.size());i++)bH[i]=a[i].val();if(!cU)for(int i=0;i<int(b.size());i++)cl[i]=b[i].val();}std::memset(bH+a.size(),0,sizeof(uint32_t)*(n-a.size()));if(!cU)std::memset(cl+b.size(),0,sizeof(uint32_t)*(n-b.size()));static constexpr cy::dn cS(998244353);const std::size_t cP=std::size_t(n)>>3;cy::fv(reinterpret_cast<__m256i*>(bH),cP,&cS);if(!cU)cy::fv(reinterpret_cast<__m256i*>(cl),cP,&cS);cy::hU(reinterpret_cast<__m256i*>(bH),reinterpret_cast<const __m256i*>(cl),cP,&cS);cy::gU<true>(reinterpret_cast<__m256i*>(bH),cP,&cS);F<e>C(bf);for(int j=0;j<bf;j++)C[j]=e::ct(bH[j]);::operator delete[](bH,std::align_val_t(32));if(!cU)::operator delete[](cl,std::align_val_t(32));return C;}
#pragma GCC pop_options
#endif
}template<class e>F<e>ie(const F<e>&a,const F<e>&b){if(a.empty()||b.empty())return{};F<e>C(a.size()+b.size()-1);if(a.size()<b.size()){for(int i=0;i<int(a.size());i++){for(int j=0;j<int(b.size());j++)C[i+j]+=a[i]*b[j];}}else{for(int j=0;j<int(b.size());j++){for(int i=0;i<int(a.size());i++)C[i+j]+=a[i]*b[j];}}return C;}template<class e>F<e>gB(const F<e>&a,const F<e>&b){const int bf=int(a.size()+b.size()-1);int n=1;while(n<bf)n<<=1;assert((e::o()-1)%uint32_t(n)==0);
#ifdef M1UNE_FPS_HAS_X86_SIMD
if constexpr(e::o()==998244353){if(n>=64&&__builtin_cpu_supports("avx2"))return internal::hT(a,b);}
#endif
const H cU=&a==&b;F<e>fa(n);std::copy(a.begin(),a.end(),fa.begin());internal::cI(fa,false);const e eN=e(n).inv();if(cU){for(int i=0;i<n;i++)fa[i]*=fa[i]*eN;}else{F<e>fb(n);std::copy(b.begin(),b.end(),fb.begin());internal::cI(fb,false);for(int i=0;i<n;i++)fa[i]*=fb[i]*eN;}internal::cI(fa,true,false);fa.resize(bf);return fa;}namespace internal{template<class e>F<e>hP(const F<e>&a,const F<e>&b,int an){assert(e::o()==998244353);assert(an>=2&&(an&(an-1))==0);assert((e::o()-1)%uint32_t(an)==0);const int bo=an/2;const int ds=int((a.size()+bo-1)/bo);const int dt=int((b.size()+bo-1)/bo);auto ed=[&](const F<e>&aq,int eh){F<F<e>>dx;dx.reserve(eh);for(int V=0;V<eh;V++){const int begin=V*bo;const int aV=std::min(bo,int(aq.size())-begin);F<e>cw(an);std::copy_n(aq.begin()+begin,aV,cw.begin());cI(cw,false);dx.emplace_back(std::move(cw));}return dx;};F<F<e>>bH=ed(a,ds);F<F<e>>cl=ed(b,dt);const int bf=int(a.size()+b.size()-1);F<e>C(bf);F<e>bv(an);for(int bK=0;bK<ds+dt-1;bK++){std::fill(bv.begin(),bv.end(),e(0));const int fC=std::max(0,bK-(dt-1));const int fG=std::min(ds-1,bK);for(int cB=fC;cB<=fG;cB++){const int fB=bK-cB;for(int i=0;i<an;i++)bv[i]+=bH[cB][i]*cl[fB][i];}cI(bv,true);const int dQ=bK*bo;const int fo=std::min(an,bf-dQ);for(int i=0;i<fo;i++)C[dQ+i]+=bv[i];}return C;}
#ifdef M1UNE_FPS_HAS_X86_SIMD
class bm{private:uint32_t*ch;public:explicit bm(std::size_t bz):ch(static_cast<uint32_t*>(::operator new[](sizeof(uint32_t)*bz,std::align_val_t(32)))){}bm(const bm&)=delete;bm&operator=(const bm&)=delete;bm(bm&&dX)noexcept:ch(dX.ch){dX.ch=nullptr;}bm&operator=(bm&&dX)noexcept{if(this==&dX)return*this;::operator delete[](ch,std::align_val_t(32));ch=dX.ch;dX.ch=nullptr;return*this;}~bm(){::operator delete[](ch,std::align_val_t(32));}uint32_t*data(){return ch;}const uint32_t*data()const{return ch;}};template<class e>__attribute__((target("avx2,bmi"),hot))F<e>hQ(const F<e>&a,const F<e>&b,int an){assert(e::o()==998244353);assert(an>=64&&(an&(an-1))==0);assert((e::o()-1)%uint32_t(an)==0);const int bo=an/2;const int ds=int((a.size()+bo-1)/bo);const int dt=int((b.size()+bo-1)/bo);static constexpr cy::dn cS(998244353);const std::size_t cP=std::size_t(an)/8;auto ed=[&](const F<e>&aq,int eh){F<bm>dx;dx.reserve(eh);for(int V=0;V<eh;V++){const int begin=V*bo;const int aV=std::min(bo,int(aq.size())-begin);bm cw(an);if constexpr(std::is_same_v<e,ci::R<998244353>>){static_assert(sizeof(e)==sizeof(uint32_t)&&std::is_trivially_copyable_v<e>);std::memcpy(cw.data(),aq.data()+begin,sizeof(uint32_t)*aV);}else{for(int i=0;i<aV;i++)cw.data()[i]=aq[begin+i].val();}std::memset(cw.data()+aV,0,sizeof(uint32_t)*(an-aV));cy::fv(reinterpret_cast<__m256i*>(cw.data()),cP,&cS);dx.emplace_back(std::move(cw));}return dx;};F<bm>bH=ed(a,ds);F<bm>cl=ed(b,dt);const int bf=int(a.size()+b.size()-1);F<e>C(bf);bm bv(an);for(int bK=0;bK<ds+dt-1;bK++){std::memset(bv.data(),0,sizeof(uint32_t)*an);const int fC=std::max(0,bK-(dt-1));const int fG=std::min(ds-1,bK);for(int cB=fC;cB<=fG;cB++){const int fB=bK-cB;cy::hS(reinterpret_cast<__m256i*>(bv.data()),reinterpret_cast<const __m256i*>(bH[cB].data()),reinterpret_cast<const __m256i*>(cl[fB].data()),cP,&cS);}cy::gU<true>(reinterpret_cast<__m256i*>(bv.data()),cP,&cS);const int dQ=bK*bo;const int fo=std::min(an,bf-dQ);for(int i=0;i<fo;i++){uint32_t w=C[dQ+i].val()+bv.data()[i];if(w>=e::o())w-=e::o();C[dQ+i]=e::ct(w);}}return C;}
#endif
template<class e>F<e>hR(const F<e>&a,const F<e>&b,int an=1<<23){
#ifdef M1UNE_FPS_HAS_X86_SIMD
if(an>=64&&__builtin_cpu_supports("avx2"))return hQ(a,b,an);
#endif
return hP(a,b,an);}}template<class e>F<e>gP(const F<e>&a,const F<e>&b){if(a.empty()||b.empty())return{};if(std::min(a.size(),b.size())<=32)return ie(a,b);const int bf=int(a.size()+b.size()-1);int n=1;while(n<bf)n<<=1;if constexpr(internal::eA<e>::value){if constexpr(e::o()==998244353){if(n>(1<<23))return internal::hR(a,b);}if((e::o()-1)%uint32_t(n)==0)return gB(a,b);}using dW=ci::R<167772161>;using cn=ci::R<469762049>;using bM=ci::R<754974721>;assert(n<=(1<<24));[[maybe_unused]]const unsigned __int128 ic=static_cast<unsigned __int128>(std::min(a.size(),b.size()))*(e::o()-1)*(e::o()-1);[[maybe_unused]]const unsigned __int128 ix=static_cast<unsigned __int128>(dW::o())*cn::o()*bM::o();assert(ic<ix);auto ff=[&]<class eM>(){F<eM>gN(a.size());F<eM>gO(b.size());for(int i=0;i<int(a.size());i++)gN[i]=eM(a[i].val());for(int i=0;i<int(b.size());i++)gO[i]=eM(b[i].val());return gB(gN,gO);};F<dW>c1=ff.template operator()<dW>();F<cn>c2=ff.template operator()<cn>();F<bM>c3=ff.template operator()<bM>();static const uint64_t ih=cn(dW::o()).inv().val();static const uint64_t gX=dW::o()%bM::o();static const uint64_t in=gX*(cn::o()%bM::o())%bM::o();static const uint64_t hX=bM(uint32_t(in)).inv().val();const uint64_t cQ=e::o();const uint64_t gR=dW::o()%cQ;const uint64_t ij=gR*(cn::o()%cQ)%cQ;F<e>C(bf);for(int i=0;i<bf;i++){const uint64_t r1=c1[i].val();const uint64_t r2=c2[i].val();const uint64_t r3=c3[i].val();const uint64_t ah=(r2+cn::o()-r1%cn::o())%cn::o()*ih%cn::o();const uint64_t ip=(r1%bM::o()+gX*(ah%bM::o()))%bM::o();const uint64_t ao=(r3+bM::o()-ip)%bM::o()*hX%bM::o();uint64_t w=r1%cQ;w=(w+gR*(ah%cQ))%cQ;w=(w+ij*(ao%cQ))%cQ;C[i]=e::ct(uint32_t(w));}return C;}}}
#ifdef M1UNE_FPS_HAS_X86_SIMD
#undef M1UNE_FPS_HAS_X86_SIMD
#endif
namespace aI{namespace ci{namespace internal{inline uint64_t eg(uint64_t a,uint64_t b,uint64_t o){return static_cast<uint64_t>(static_cast<unsigned __int128>(a)*b%o);}inline uint64_t gY(uint64_t aW,uint64_t au,uint64_t o){uint64_t C=1;while(au>0){if(au&1)C=eg(C,aW,o);aW=eg(aW,aW,o);au>>=1;}return C;}inline uint64_t gE(){static uint64_t ht=0x123456789abcdef0ULL;ht+=0x9e3779b97f4a7c15ULL;uint64_t w=ht;w=(w^(w>>30))*0xbf58476d1ce4e5b9ULL;w=(w^(w>>27))*0x94d049bb133111ebULL;return w^(w>>31);}}inline H iJ(uint64_t w){if(w<2)return false;for(uint64_t dc:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}){if(w%dc==0)return w==dc;}uint64_t cT=w-1;int gL=0;while((cT&1)==0){cT>>=1;gL++;}for(uint64_t aW:{2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL}){if(aW%w==0)continue;uint64_t x=internal::gY(aW%w,cT,w);if(x==1||x==w-1)continue;H gV=true;for(int i=1;i<gL;i++){x=internal::eg(x,x,w);if(x==w-1){gV=false;break;}}if(gV)return false;}return true;}namespace internal{inline uint64_t iA(uint64_t w){for(uint64_t dc:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}){if(w%dc==0)return dc;}while(true){const uint64_t iI=gE()%(w-1)+1;uint64_t y=gE()%(w-1)+1;uint64_t x=0;uint64_t dT=0;uint64_t dh=1;uint64_t eE=1;auto fA=[&](uint64_t ha){return static_cast<uint64_t>((static_cast<unsigned __int128>(eg(ha,ha,w))+iI)%w);};while(dh==1){x=y;for(uint64_t i=0;i<eE;i++)y=fA(y);for(uint64_t ab=0;ab<eE&&dh==1;ab+=128){dT=y;uint64_t bL=1;const uint64_t V=std::min<uint64_t>(128,eE-ab);for(uint64_t i=0;i<V;i++){y=fA(y);const uint64_t ft=x>y?x-y:y-x;bL=eg(bL,ft,w);}dh=std::gcd(bL,w);}eE<<=1;}if(dh==w){do{dT=fA(dT);const uint64_t ft=x>dT?x-dT:dT-x;dh=std::gcd(ft,w);}while(dh==1);}if(dh!=w)return dh;}}inline P fi(uint64_t w,F<uint64_t>&dw){if(w==1)return;if(iJ(w)){dw.push_back(w);return;}const uint64_t hb=iA(w);fi(hb,dw);fi(w/hb,dw);}}inline F<uint64_t>iq(uint64_t w){assert(w>=1);F<uint64_t>C;internal::fi(w,C);std::sort(C.begin(),C.end());return C;}inline F<std::pair<uint64_t,int>>ef(uint64_t w){F<uint64_t>dw=iq(w);F<std::pair<uint64_t,int>>C;for(uint64_t dc:dw){if(C.empty()||C.back().first!=dc){C.emplace_back(dc,1);}else{C.back().second++;}}return C;}inline F<uint64_t>eP(uint64_t w){F<uint64_t>C={1};for(const auto&cD:ef(w)){const int it=int(C.size());uint64_t bV=1;for(int au=1;au<=cD.second;au++){bV*=cD.first;for(int i=0;i<it;i++){C.push_back(C[i]*bV);}}}std::sort(C.begin(),C.end());return C;}inline uint64_t iD(uint64_t w){assert(w>=1);uint64_t C=w;for(const auto&cD:ef(w)){C=C/cD.first*(cD.first-1);}return C;}inline int jz(uint64_t w){assert(w>=1);int C=1;for(const auto&cD:ef(w)){if(cD.second>=2)return 0;C=-C;}return C;}}}namespace aI{namespace ci{inline H ib(uint64_t o){if(o==2||o==4)return true;if(o<2)return false;uint64_t cT=o;if((cT&1)==0){cT>>=1;if((cT&1)==0)return false;}return ef(cT).size()==1;}inline uint64_t fl(uint64_t o){assert(o>=2);if(o==2)return 1;if(!ib(o))return 0;const uint64_t hC=iD(o);const F<std::pair<uint64_t,int>>dw=ef(hC);for(uint64_t ej=2;ej<o;ej++){if(std::gcd(ej,o)!=1)continue;H dS=true;for(const auto&cD:dw){if(internal::gY(ej,hC/cD.first,o)==1){dS=false;break;}}if(dS)return ej;}return 0;}}}namespace aI{namespace ci{namespace internal{template<class T>struct bt{using dq=T;static constexpr int da=0;};template<class T,class iC>struct bt<F<T,iC>>{using dq=typename bt<T>::dq;static constexpr int da=bt<T>::da+1;};template<class ak>P fh(const ak&aq,F<int>&aP){if constexpr(bt<ak>::da>0){assert(!aq.empty());assert(aq.size()<=std::size_t(std::numeric_limits<int>::max()));aP.push_back(int(aq.size()));fh(aq.front(),aP);}}template<class ak,class e>P fg(const ak&aq,const F<int>&aP,int bx,F<e>&cz){if constexpr(bt<ak>::da==0){cz.push_back(aq);}else{assert(bx<int(aP.size()));assert(int(aq.size())==aP[bx]);for(const auto&fK:aq){fg(fK,aP,bx+1,cz);}}}template<class ak,class e>P gr(ak&aq,const F<int>&aP,int bx,const F<e>&cz,int&ce){if constexpr(bt<ak>::da==0){assert(ce<int(cz.size()));aq=cz[ce++];}else{assert(bx<int(aP.size()));aq.resize(aP[bx]);for(auto&fK:aq){gr(fK,aP,bx+1,cz,ce);}}}template<class ak>F<int>gp(const ak&ah,const ak&ao,F<typename bt<ak>::dq>&dm,F<typename bt<ak>::dq>&dl){F<int>aP;fh(ah,aP);assert(int(aP.size())==bt<ak>::da);F<int>gM;fh(ao,gM);assert(gM==aP);fg(ah,aP,0,dm);fg(ao,aP,0,dl);std::reverse(aP.begin(),aP.end());return aP;}template<class ak>ak gq(F<int>as,const F<typename bt<ak>::dq>&cz){std::reverse(as.begin(),as.end());ak C;int ce=0;gr(C,as,0,cz,ce);assert(ce==int(cz.size()));return C;}inline int ey(const F<int>&as){int64_t aV=1;for(int aB:as){assert(aB>0);aV*=aB;assert(aV<=std::numeric_limits<int>::max());}return int(aV);}inline F<int>ia(const F<int>&as){const int bG=int(as.size());const int aU=ey(as);F<int>dz(aU);if(bG==0)return dz;for(int bN=0;bN<aU;bN++){int hF=0;int aO=1;for(int aE=0;aE+1<bG;aE++){aO*=as[aE];hF+=bN/aO;}dz[bN]=hF%bG;}return dz;}template<class e>F<e>hY(const F<e>&fu,e ratio){const int bz=int(fu.size());if(bz<=64){F<e>C(bz);e hr=1;for(int i=0;i<bz;i++){e bV=1;for(const e&iw:fu){C[i]+=iw*bV;bV*=hr;}hr*=ratio;}return C;}auto gy=[](e aW,int cX){F<e>C(cX);if(cX==0)return C;C[0]=1;e bV=1;for(int i=0;i+1<cX;i++){C[i+1]=C[i]*bV;bV*=aW;}return C;};F<e>iK=gy(ratio,2*bz-1);F<e>bw=gy(ratio.inv(),bz);F<e>eT(fu);for(int i=0;i<bz;i++)eT[i]*=bw[i];std::reverse(eT.begin(),eT.end());F<e>bL=cH::gP(eT,iK);F<e>C(bz);for(int i=0;i<bz;i++)C[i]=bL[bz-1+i]*bw[i];return C;}template<class e>F<e>fe(F<e>aq,e ratio,H fD){if constexpr(cH::internal::eA<e>::value){const int bz=int(aq.size());if((bz&(bz-1))==0){cH::internal::cI(aq,fD,false);return aq;}}return hY(aq,ratio);}}template<class e>F<e>go(const F<int>&as,const F<e>&ah,const F<e>&ao){static_assert(cH::internal::eA<e>::value,"truncated multivariate convolution requires a static-modulus type");const int bG=int(as.size());const int aU=internal::ey(as);assert(int(ah.size())==aU);assert(int(ao.size())==aU);if(bG==0)return{ah[0]*ao[0]};int64_t eB=1;while(eB<2LL*aU-1)eB<<=1;assert(eB<=std::numeric_limits<int>::max());const int an=int(eB);assert((e::o()-1)%uint32_t(an)==0);const F<int>dz=internal::ia(as);F<F<e>>bZ(bG,F<e>(an));F<F<e>>dk(bG,F<e>(an));for(int i=0;i<aU;i++){bZ[dz[i]][i]=ah[i];dk[dz[i]][i]=ao[i];}for(int db=0;db<bG;db++){cH::internal::cI(bZ[db],false);cH::internal::cI(dk[db],false);}F<F<e>>bv(bG,F<e>(an));for(int cp=0;cp<bG;cp++){for(int co=0;co<bG;co++){F<e>&iy=bv[(cp+co)%bG];const F<e>&iz=bZ[cp];const F<e>&iv=dk[co];for(int i=0;i<an;i++){iy[i]+=iz[i]*iv[i];}}}for(int db=0;db<bG;db++){cH::internal::cI(bv[db],true);}F<e>C(aU);for(int i=0;i<aU;i++){C[i]=bv[dz[i]][i];}return C;}template<class ak,std::enable_if_t<(internal::bt<ak>::da>0),int> =0>ak go(const ak&ah,const ak&ao){using e=typename internal::bt<ak>::dq;F<e>dm,dl;F<int>as=internal::gp(ah,ao,dm,dl);F<e>fk=go(as,dm,dl);return internal::gq<ak>(std::move(as),fk);}template<class e>F<e>ex(const F<int>&as,const F<e>&ah,const F<e>&ao){const int aU=internal::ey(as);assert(int(ah.size())==aU);assert(int(ao.size())==aU);if(as.empty())return{ah[0]*ao[0]};const uint32_t cC=e::o();H gH=true;for(int aB:as){if((cC-1)%uint32_t(aB)!=0)gH=false;}if(!gH){F<int>bF;for(int aB:as){if(aB!=1)bF.push_back(aB);}if(bF.empty())return{ah[0]*ao[0]};F<int>dP(bF.size());for(int i=0;i<int(bF.size());i++){const int64_t hf=2LL*bF[i]-1;assert(hf<=std::numeric_limits<int>::max());dP[i]=int(hf);}const int eH=internal::ey(dP);int64_t ez=0;int64_t fm=1;for(int aE=0;aE<int(bF.size());aE++){ez+=int64_t(bF[aE]-1)*fm;fm*=dP[aE];}assert(fm==eH);assert(2*ez+1==eH);assert(ez<std::numeric_limits<int>::max());const int gs=int(ez)+1;F<e>gJ(gs);F<e>gG(gs);for(int bN=0;bN<aU;bN++){int cd=bN;int cN=0;int gz=1;for(int aE=0;aE<int(bF.size());aE++){const int fs=cd%bF[aE];cd/=bF[aE];cN+=fs*gz;gz*=dP[aE];}gJ[cN]=ah[bN];gG[cN]=ao[bN];}F<e>gC=cH::gP(gJ,gG);assert(int(gC.size())==eH);F<e>C(aU);for(int cN=0;cN<eH;cN++){int cd=cN;int bN=0;int aO=1;for(int aE=0;aE<int(bF.size());aE++){const int fs=cd%dP[aE];cd/=dP[aE];bN+=(fs%bF[aE])*aO;aO*=bF[aE];}C[bN]+=gC[cN];}return C;}const uint64_t dS=fl(cC);assert(dS!=0);F<e>bZ(ah);F<e>dk(ao);int aO=1;for(int aB:as){assert((cC-1)%uint32_t(aB)==0);const e cr=e(dS).pow((cC-1)/aB);for(int V=0;V<aU;V+=aO*aB){for(int ab=0;ab<aO;ab++){F<e>eK(aB);F<e>eI(aB);for(int i=0;i<aB;i++){eK[i]=bZ[V+ab+aO*i];eI[i]=dk[V+ab+aO*i];}eK=internal::fe(std::move(eK),cr,false);eI=internal::fe(std::move(eI),cr,false);for(int i=0;i<aB;i++){bZ[V+ab+aO*i]=eK[i];dk[V+ab+aO*i]=eI[i];}}}aO*=aB;}for(int i=0;i<aU;i++){bZ[i]*=dk[i];}aO=1;for(int aB:as){const e cO=e(dS).pow((cC-1)/aB).inv();for(int V=0;V<aU;V+=aO*aB){for(int ab=0;ab<aO;ab++){F<e>eW(aB);for(int i=0;i<aB;i++){eW[i]=bZ[V+ab+aO*i];}eW=internal::fe(std::move(eW),cO,true);for(int i=0;i<aB;i++){bZ[V+ab+aO*i]=eW[i];}}}aO*=aB;}const e iu=e(aU).inv();for(e&w:bZ)w*=iu;return bZ;}template<class ak,std::enable_if_t<(internal::bt<ak>::da>0),int> =0>ak ex(const ak&ah,const ak&ao){using e=typename internal::bt<ak>::dq;F<e>dm,dl;F<int>as=internal::gp(ah,ao,dm,dl);F<e>fk=ex(as,dm,dl);return internal::gq<ak>(std::move(as),fk);}}}using eq=aI::ci::il;P iR(){ll X,Y,Z;fW(X,Y,Z);vv(string,A,Z,Y);vv(string,B,Z,Y);FOR(z,Z)FOR(y,Y){fW(A[z][y]);}FOR(z,Z)FOR(y,Y){fW(B[z][y]);}vvv(eq,A_black,Z,Y,X,0);vvv(eq,A_white,Z,Y,X,0);vvv(eq,inv_B_black,Z,Y,X,0);vvv(eq,inv_B_white,Z,Y,X,0);FOR(z,Z)FOR(y,Y)FOR(x,X){if(A[z][y][x]=='B'){A_black[z][y][x]=1;}if(A[z][y][x]=='W'){A_white[z][y][x]=1;}}FOR(z,Z)FOR(y,Y)FOR(x,X){if(B[z][y][x]=='B'){inv_B_black[Z-z-1][Y-y-1][X-x-1]=1;}if(B[z][y][x]=='W'){inv_B_white[Z-z-1][Y-y-1][X-x-1]=1;}}auto C1=aI::ci::ex(A_black,inv_B_white);auto C2=aI::ci::ex(A_white,inv_B_black);ll hw=bj<ll>;FOR(z,Z)FOR(y,Y)FOR(x,X){eq c=C1[z][y][x]+C2[z][y][x];iO(hw,c.val());}fM(hw);}int main(){CPP_DUMP_SET_OPTION(max_line_width,80);CPP_DUMP_SET_OPTION(log_label_func,cpp_dump::log_label::filename());CPP_DUMP_SET_OPTION(enable_asterisk,true);int T=1;while(T--)iR();return 0;}