using H=bool;using P=void;using Q=unsigned char;using ae=long double;using ai=unsigned;using aj=char;using aq=long long;using as=__uint128_t;using av=unsigned long long;using ax=__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 eN{namespace internal{template<class T,class=P>struct gY:std::false_type{};template<class T>struct gY<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=gY<T>::value;template<class T>using ig=decltype(*std::begin(std::declval<T&>()));template<class T>using ip=std::remove_cv_t<std::remove_reference_t<ig<T>>>;template<class T,class=P>struct gv{using type=ip<T>;};template<class T>struct gv<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 gs=typename gv<T>::type;template<class T>struct gH:std::false_type{};template<class T,std::size_t N>struct gH<T[N]>:std::bool_constant<std::is_same_v<std::remove_cv_t<T>,aj>>{};template<class T>struct ik: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*>||gH<std::remove_reference_t<T>>::value>{};template<class T>inline constexpr H eC=ik<T>::value;template<class T,class=P>struct gC:std::false_type{};template<class T>struct gC<T,std::void_t<decltype(std::declval<const T&>().val())>>:std::true_type{};template<class T>inline constexpr H gz=gC<T>::value;template<class T,class=P>struct gu:std::false_type{};template<class T>struct gu<T,std::void_t<decltype(T::o()),decltype(T::ct(std::declval<uint32_t>()))>>:std::true_type{};template<class T>inline constexpr H hX=gu<T>::value;template<class T>inline constexpr H eF=std::is_integral_v<T>||std::is_same_v<std::remove_cv_t<T>,ax>||std::is_same_v<std::remove_cv_t<T>,as>;template<class T>inline constexpr H fq=std::is_signed_v<T>||std::is_same_v<std::remove_cv_t<T>,ax>;template<class T>struct fn{using type=std::make_unsigned_t<T>;};template<>struct fn<ax>{using type=as;};template<>struct fn<as>{using type=as;};template<class T>using ii=typename fn<std::remove_cv_t<T>>::type;}struct cP{static constexpr int bZ=1<<20;private:std::FILE*du;aj aD[bZ];int ac;int bh;int eB;H fr;H hk(){ac=0;if(fr){ssize_t cV;do{cV=::read(eB,aD,bZ);}while(cV<0&&errno==EINTR);if(cV<=0){bh=0;return false;}bh=int(cV);}else{bh=int(std::fread(aD,1,bZ,du));}return bh!=0;}template<class T>H hV(T&w){if(!eI())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 im(){if(bh-ac>=64)return true;const int cb=bh-ac;if(cb>0)std::memmove(aD,aD+ac,cb);const int iM=int(std::fread(aD+cb,1,bZ-cb,du));ac=0;bh=cb+iM;if(bh<bZ)aD[bh]='\0';return bh!=0;}public:explicit cP(std::FILE*eT=stdin):du(eT),ac(0),bh(0),eB(::fileno(eT)),fr([&]{struct stat hm;return eB>=0&&::fstat(eB,&hm)==0&&!S_ISREG(hm.st_mode);}()){}cP(const cP&)=delete;cP&operator=(const cP&)=delete;int bn(){if(ac==bh&&!hk())return EOF;return aD[ac++];}H eI(){int c=bn();while(c!=EOF&&c<=' ')c=bn();if(c==EOF)return false;--ac;return true;}H read(aj&w){if(!eI())return false;w=aj(bn());return true;}H read(std::string&w){if(!eI())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(!hk())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::eF<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 hV(w);if(!im())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(!eI())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 hp=0.1L;c=bn();while('0'<=c&&c<='9'){C+=(c-'0')*hp;hp*=0.1L;c=bn();}}if(c=='e'||c=='E'){c=bn();H gw=false;if(c=='-'||c=='+'){gw=c=='-';c=bn();}int at=0;while('0'<=c&&c<='9'){at=at*10+(c-'0');c=bn();}ae fO=1;ae bU=10;while(at>0){if(at&1)fO*=bU;bU*=bU;at>>=1;}C=gw?C/fO:C*fO;}w=static_cast<T>(bw?-C:C);return true;}template<class T>std::enable_if_t<internal::gz<T>&&!internal::eF<T>&&!internal::dR<T>,H>read(T&w){aq x;if(!read(x))return false;if constexpr(internal::hX<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 dx,class eo>H read(std::pair<dx,eo>&w){if(!read(w.first))return false;return read(w.second);}template<class cE>std::enable_if_t<internal::dR<cE>&&!internal::eC<cE>,H>read(cE&fN){using dn=internal::gs<cE>;constexpr H eR=internal::dR<dn>&&!internal::eC<dn>;for(auto&&w:fN){if constexpr(std::is_same_v<dn,H>&&!eR){H x;if(!read(x))return false;w=x;}else{if(!read(w))return false;}}return true;}template<class dx,class eo,class...fP>H read(dx&ah,eo&ao,fP&...rest){if(!read(ah))return false;return read(ao,rest...);}template<class T>cP&operator>>(T&w){if(!read(w))std::abort();return*this;}};struct cx{static constexpr int bZ=1<<20;private:inline static const auto gP=[]{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*du;aj aD[bZ];int ac;int ei;std::chars_format eE;aj fj;public:explicit cx(std::FILE*eT=stdout):du(eT),ac(0),ei(6),eE(std::chars_format::general),fj(' '){}cx(const cx&)=delete;cx&operator=(const cx&)=delete;~cx(){eU();}P eU(){if(ac!=0){std::fwrite(aD,1,ac,du);ac=0;}std::fflush(du);}P ca(aj c){if(ac==bZ)eU();aD[ac++]=c;}P bk(const aj*s){while(*s!='\0')ca(*s++);}P bk(const std::string&s){std::size_t cd=0;while(cd<s.size()){if(ac==bZ)eU();const std::size_t fE=std::min<std::size_t>(bZ-ac,s.size()-cd);std::memcpy(aD+ac,s.data()+cd,fE);ac+=int(fE);cd+=fE;}}P bk(aj c){ca(c);}P bk(H w){ca(w?'1':'0');}template<class T>std::enable_if_t<std::is_floating_point_v<T>>bk(T w){aj dU[128];auto[end,iO]=std::to_chars(dU,dU+sizeof(dU),w,eE,ei);if(iO!=std::errc())std::abort();for(const aj*fD=dU;fD!=end;fD++){ca(*fD);}}template<class T>std::enable_if_t<internal::eF<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 hu=std::remove_cv_t<T>;using el=internal::ii<hu>;el bI;if constexpr(internal::fq<hu>){if(w<0){ca('-');bI=el(0)-el(w);}else{bI=el(w);}}else{bI=w;}if(bI==0){ca('0');return;}ai hh[16];int aV=0;while(bI>=10000){const el em=bI/10000;hh[aV++]=ai(bI-em*10000);bI=em;}if(ac>bZ-64)eU();const ai eP=ai(bI);const aj*ah=gP.data()+4*eP;int fW=eP<10?3:eP<100?2:eP<1000?1:0;for(;fW<4;fW++)aD[ac++]=ah[fW];while(aV--){const aj*dU=gP.data()+4*hh[aV];std::memcpy(aD+ac,dU,4);ac+=4;}}template<class T>std::enable_if_t<internal::gz<T>&&!internal::eF<T>&&!internal::dR<T> >bk(const T&w){bk(w.val());}template<class dx,class eo>P bk(const std::pair<dx,eo>&w){bk(w.first);ca(' ');bk(w.second);}template<class cE>std::enable_if_t<internal::dR<cE>&&!internal::eC<cE> >bk(const cE&fN){using dn=internal::gs<const cE>;constexpr H eR=internal::dR<dn>&&!internal::eC<dn>;H ah=true;for(const auto&w:fN){if(!ah)ca(eR?'\n':fj);ah=false;if constexpr(std::is_same_v<dn,H>&&!eR){bk(static_cast<H>(w));}else{bk(w);}}}template<class dx,class...fP>P fL(const dx&ah,const fP&...rest){bk(ah);((ca(' '),bk(rest)),...);}P println(){ca('\n');}P jl(int ek){ei=ek;}P jo(int ek=6){eE=std::chars_format::fixed;ei=ek;}P jm(int ek=6){eE=std::chars_format::general;ei=ek;}P jj(aj iF){fj=iF;}template<class...Args>P println(const Args&...args){fL(args...);ca('\n');}template<class T>cx&operator<<(const T&w){bk(w);return*this;}};}}using namespace std;namespace aI{namespace cm{inline eN::cP&ho(){static eN::cP fy;return fy;}inline eN::cx&cW(){static eN::cx fy;return fy;}}}using ll=aq;using K=unsigned int;using bV=av;using fS=__int128;using jH=unsigned __int128;
#ifdef __SIZEOF_FLOAT128__
using jG=__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 bV bj<bV> =bj<ll>;template<>constexpr fS bj<fS> =fS(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 ge=vector<vc<T>>;using jO=ge<int>;using jP=ge<ll>;template<class T>using iS=vector<ge<T>>;template<class T>using iR=vector<iS<T>>;template<class T>using jz=vector<iR<T>>;template<class T>using jN=std::priority_queue<T,vector<T>,greater<T>>;template<class T,class U>using jI=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 fH(int x){return __builtin_popcount(x);}int fH(K x){return __builtin_popcount(x);}int fH(ll x){return __builtin_popcountll(x);}int fH(bV 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(bV x){return __builtin_parityll(x);}int fI(int x){return(x==0?-1:31-__builtin_clz(x));}int fI(K x){return(x==0?-1:31-__builtin_clz(x));}int fI(ll x){return(x==0?-1:63-__builtin_clzll(x));}int fI(bV x){return(x==0?-1:63-__builtin_clzll(x));}int fG(int x){return(x==0?-1:__builtin_ctz(x));}int fG(K x){return(x==0?-1:__builtin_ctz(x));}int fG(ll x){return(x==0?-1:__builtin_ctzll(x));}int fG(bV x){return(x==0?-1:__builtin_ctzll(x));}template<typename T>T fK(T a,T b){return a/b-(a%b&&(a^b)<0);}template<typename T>T jE(T x,T y){return fK(x+y-1,y);}template<typename T>T jD(T x,T y){return x-y*fK(x,y);}template<typename T>pair<T,T>jw(T x,T y){T q=fK(x,y);return{q,x-q*y};}template<typename T,typename U>T jJ(U x_,int n){T x=x_;T hD=1;while(n>0){if(n&1)hD*=x;x*=x;n>>=1;}return hD;}template<typename T,typename U>T jK(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 jC(T&a,const S&b){return(a<b?a=b,1:0);}template<class T,class S>inline H iN(T&a,const S&b){return(a>b?a=b,1:0);}vc<int>jt(const string&S,aj iz){vc<int>A(S.size());FOR(i,S.size()){A[i]=(S[i]!='?'?S[i]-iz:-1);}return A;}template<typename T,typename U>vector<T>jv(vector<U>&A,int iX=1){int N=A.size();vector<T>B(N+1);FOR(i,N){B[i+1]=B[i]+A[i];}if(iX==0)B.erase(B.begin());return B;}template<typename T>vector<int>jq(const vector<T>&A){vector<int>fY(A.size());iota(all(fY),0);sort(all(fY),[&](int i,int j){return(A[i]==A[j]?i<j:A[i]<A[j]);});return fY;}template<typename T>vc<T>jn(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 iV(T...a){return iV(initializer_list<common_type_t<T...>>{a...});}template<class...T>constexpr auto iU(T...a){return iU(initializer_list<common_type_t<T...>>{a...});}template<class...Ts>H fV(Ts&...aB){return aI::cm::ho().read(aB...);}template<class...Ts>P fL(const Ts&...aB){aI::cm::cW().println(aB...);}P jA(H b){aI::cm::cW().println(b?"YES":"NO");}P jB(H b){aI::cm::cW().println(b?"Yes":"No");}P jL(){aI::cm::cW().println("YES");}P NO(){aI::cm::cW().println("NO");}P jM(){aI::cm::cW().println("Yes");}P No(){aI::cm::cW().println("No");}auto&jx=aI::cm::ho();auto&jr=aI::cm::cW();namespace aI{namespace ch{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 dt,std::enable_if_t<std::is_integral_v<dt>,int> =0>constexpr R(dt v)noexcept{if constexpr(std::is_signed_v<dt>){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(aq n)const noexcept{R eb=ct(1%bg);R x=n<0?inv():*this;uint64_t at=n<0?uint64_t(-(n+1))+1:uint64_t(n);while(at>0){if(at&1)eb*=x;x*=x;at>>=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){aq v;is>>v;O=R(v);return is;}};using ij=R<998244353>;using jk=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 ju(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 dt,std::enable_if_t<std::is_integral_v<dt>,int> =0>ag(dt v)noexcept{if constexpr(std::is_signed_v<dt>){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(aq at)const noexcept{ag C=ct(1%ba);ag aW=at<0?inv():*this;uint64_t bI=at<0?uint64_t(-(at+1))+1:uint64_t(at);while(bI>0){if(bI&1)C*=aW;aW*=aW;bI>>=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){aq 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 dD{namespace internal{namespace cy{using K=ai;using bV=av;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 jF(K x,K M){return std::min(x,x+M);}constexpr K dV(bV x,K E,K M){return(x+bV(K(x)*E)*M)>>32;}constexpr K bN(K x,K y,K E,K M){return dV(bV(x)*y,E,M);}constexpr K aJ(K x,K y,K E,K M){return dY(dV(bV(x)*y,E,M),M);}constexpr K gc(K a,K b,K E,K M,K r){for(;b;b>>=1,a=bN(a,a,E,M)){if(b&1){r=bN(r,a,E,M);}}return r;}constexpr K hr(K a,K b,K E,K M,K r){return dY(gc(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 iK(D x,D M){return _mm256_min_epu32(x,_mm256_add_epi32(x,M));}inline D ce(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 iK(_mm256_sub_epi32(x,y),M);}template<int iW>inline D js(D x,D M){return _mm256_blend_epi32(x,_mm256_sub_epi32(M,x),iW);}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 bN(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(bN(a,b,E,M),M);}inline D cT(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 bH(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 jp(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 eK(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 bT=26,dq=6;constexpr auto cX=ap(1)<<dq;static_assert(dq%2==0);struct dm{K o,cq,E,am,r2,r3,cs,eQ,dC[bT];alignas(32)std::array<K,8>eX[bT-2],eW[bT-2],fR,fX,fQ,et[bT-3],hl[bT-3],er[bT-3],hd[bT-3],ga,gb,hi,hj,fT,hb,fU,hc;constexpr dm(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((-bV(m))%m),r3(aJ(r2,r2,E,m)),cs{},eQ{},dC{},eX{},eW{},fR{},fX{},fQ{},et{},hl{},er{},hd{},ga{},gb{},hi{},hj{},fT{},hb{},fU{},hc{}{const int k=__builtin_ctz(m-1);K _g=bN(3,r2,E,o);for(;;++_g){if(hr(_g,o>>1,E,o,am)!=am){break;}}_g=gc(_g,o>>k,E,o,am);K bq[bT-1],bl[bT-1];bq[k-2]=_g,bl[k-2]=gc(_g,o-2,E,o,am);for(int i=k-2;i>0;--i){bq[i-1]=bN(bq[i],bq[i],E,o);bl[i-1]=bN(bl[i],bl[i],E,o);}dC[k-1]=hr(_g,3,E,o,am);for(int i=k-1;i>0;--i){dC[i-1]=aJ(dC[i],dC[i],E,o);}cs=bq[0],eQ=cs*E;fR={am,0,am,0,am};fX={bq[1],0,bq[0],0,o-aJ(bq[0],bq[1],E,o)};fQ={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),gd=aJ(ri,ri,E,o);const K r3=aJ(r,r2,E,o),hC=aJ(ri,gd,E,o);eX[i]={r*E,r,r2*E,r2,r3*E,r3};eW[i]={ri*E,ri,gd*E,gd,hC*E,hC};pr=bN(pr,bl[i+1],E,o),dE=bN(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){hl[i][j]=et[i][j]*E;hd[i][j]=er[i][j]*E;}pr=bN(pr,bl[i+2],E,o),dE=bN(dE,bq[i+2],E,o);}ga={am,am,am,cs,am,am,am,cs};gb={am,am,am,am,am,bq[1],cs,aJ(cs,bq[1],E,o)};const K ea=o-r2,hn=aJ(cs,r2,E,o);fT={ea,ea,ea,hn,ea,ea,ea,hn};fU={am,am,am,am,am,bl[1],bl[0],aJ(bl[0],bl[1],E,o)};for(int j=0;j<8;++j){hi[j]=ga[j]*E,hj[j]=gb[j]*E;hb[j]=fT[j]*E,hc[j]=fU[j]*E;}}};inline P fv(D*const f,const ap n,const dm*al){alignas(32)std::array<K,8>bp[bT>>1];const D ad=_mm256_set1_epi32(al->o),G=_mm256_set1_epi32(al->cq),bc=_mm256_set1_epi32(al->E);const D dc=_mm256_set1_epi32(al->cs),cU=_mm256_set1_epi32(al->eQ),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->fX);const ap nn=n>>(dZ&1),m=std::min(n,cX),mm=std::min(nn,cX);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=bH(bi(f1,f3,G),dc,cU,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=ce(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(dq,dZ):__builtin_ctzll(j))&-2,p=(t-2)>>1;for(ap L=(ap(1)<<t)>>2;L>=cX;L>>=2,t-=2,--p){auto rt=W(bp+p);const auto r1=_mm256_permutevar8x32_epi32(rt,id);const auto dz=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bc),id);rt=eK(rt,W(al->eX+__builtin_ctzll(~j>>t)),ad);const auto r2=_mm256_shuffle_epi32(r1,_MM_PERM_BBBB),fZ=_mm256_shuffle_epi32(r1,_MM_PERM_DDDD);const auto fM=_mm256_shuffle_epi32(dz,_MM_PERM_BBBB),iL=_mm256_shuffle_epi32(dz,_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=bH(f1,r1,dz,ad),es=bH(f3,fZ,iL,ad);const auto g2=bH(f2,r2,fM,ad),g0=aN(f0,G);const auto h3=bH(ce(g1,es,G),dc,cU,ad),h1=by(g1,es,G);const auto h0=aH(g0,g2,G),h2=by(g0,g2,G);const auto u0=ce(h0,h1,G),u1=bi(h0,h1,G);const auto u2=ce(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 fZ=_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=cT(f1,r1,bc,ad),es=cT(f3,fZ,bc,ad);const auto g2=cT(f2,r2,bc,ad),g0=aN(f0,G);const auto h3=bH(ce(g1,es,G),dc,cU,ad),h1=by(g1,es,G);const auto h0=aH(g0,g2,G),h2=by(g0,g2,G);const auto u0=ce(h0,h1,G),u1=bi(h0,h1,G);const auto u2=ce(h2,h3,G),u3=bi(h2,h3,G);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}rt=eK(rt,W(al->eX+__builtin_ctzll(~k)),ad);}af(bp+p,rt);}}}template<H dY=false>inline P gT(D*const f,ap n,const dm*const al){alignas(32)std::array<K,8>bp[bT>>1];const D ad=_mm256_set1_epi32(al->o),G=_mm256_set1_epi32(al->cq),bc=_mm256_set1_epi32(al->E);const D dc=_mm256_set1_epi32(al->cs),cU=_mm256_set1_epi32(al->eQ),id=_mm256_setr_epi32(0,2,0,4,0,2,0,4);const int dZ=__builtin_ctzll(n);std::fill(bp,bp+(dq>>1),al->fR);std::fill(bp+(dq>>1),bp+(bT>>1),al->fQ);const ap nn=n>>(dZ&1),mm=std::min(nn,cX);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=bH(bi(f3,f2,G),dc,cU,ad);const auto h0=ce(g0,g2,G),h1=ce(g1,g3,G);const auto h2=bi(g0,g2,G),h3=bi(g1,g3,G);const auto u0=aN(h0,G),u1=cT(h1,r1,bc,ad);const auto u2=cT(h2,r2,bc,ad),u3=cT(h3,r3,bc,ad);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}rt=eK(rt,W(al->eW+__builtin_ctzll(~k)),ad);}af(bp+p,rt);}int tt=std::min(__builtin_ctzll(~(j>>dq))+dq,dZ);for(ap L=cX,l=L<<2;t<=tt;L=l,l<<=2,t+=2,++p){if((j+cX)==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=bH(bi(f3,f2,G),dc,cU,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=bH(bi(f3,f2,G),dc,cU,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 dz=_mm256_permutevar8x32_epi32(_mm256_mul_epu32(rt,bc),id);rt=eK(rt,W(al->eW+__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 fM=_mm256_shuffle_epi32(dz,_MM_PERM_BBBB),iP=_mm256_shuffle_epi32(dz,_MM_PERM_DDDD);af(bp+p,rt);for(ap i=0;i<L;++i){auto const p0=f+j+cX-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=bH(bi(f3,f2,G),dc,cU,ad);const auto h0=ce(g0,g2,G),h1=ce(g1,g3,G);const auto h2=bi(g0,g2,G),h3=bi(g1,g3,G);const auto u0=aN(h0,G),u1=bH(h1,r1,dz,ad);const auto u2=bH(h2,r2,fM,ad),u3=bH(h3,r3,iP,ad);af(p0,u0),af(p1,u1),af(p2,u2),af(p3,u3);}}}}if(dY&&nn==n&&n<=cX){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 gV(const D*f,const D*g,D ww,D fx,D bc,D ad,D G){const auto iY=W(f),iZ=W(g);const auto hF=aN(iY,G),bb=aN(cT(iZ,fx,bc,ad),ad);const auto aw=aN(cT(hF,ww,bc,ad),ad);const auto aa=aN(hF,ad);const auto de=_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 hA=_mm256_alignr_epi8(aa,de,12);auto cF=_mm256_mul_epu32(a0,b0);auto cG=_mm256_mul_epu32(a1,b0);auto dA=_mm256_mul_epu32(hA,b1);auto dB=_mm256_mul_epu32(a0,b1);const auto b2=_mm256_permute4x64_epi64(bb,0x55),b3=_mm256_shuffle_epi32(b2,_MM_PERM_CDAB);const auto hz=_mm256_alignr_epi8(aa,de,8);const auto hy=_mm256_alignr_epi8(aa,de,4);cF=_mm256_add_epi64(cF,_mm256_mul_epu32(hz,b2));cG=_mm256_add_epi64(cG,_mm256_mul_epu32(hA,b2));dA=_mm256_add_epi64(dA,_mm256_mul_epu32(hy,b3));dB=_mm256_add_epi64(dB,_mm256_mul_epu32(hz,b3));const auto b4=_mm256_permute4x64_epi64(bb,0xaa),b5=_mm256_shuffle_epi32(b4,_MM_PERM_CDAB);const auto hx=_mm256_alignr_epi8(de,aw,12);cF=_mm256_add_epi64(cF,_mm256_mul_epu32(de,b4));cG=_mm256_add_epi64(cG,_mm256_mul_epu32(hy,b4));dA=_mm256_add_epi64(dA,_mm256_mul_epu32(hx,b5));dB=_mm256_add_epi64(dB,_mm256_mul_epu32(de,b5));const auto b6=_mm256_permute4x64_epi64(bb,0xff),b7=_mm256_shuffle_epi32(b6,_MM_PERM_CDAB);const auto hw=_mm256_alignr_epi8(de,aw,8);const auto iT=_mm256_alignr_epi8(de,aw,4);cF=_mm256_add_epi64(cF,_mm256_mul_epu32(hw,b6));cG=_mm256_add_epi64(cG,_mm256_mul_epu32(hx,b6));dA=_mm256_add_epi64(dA,_mm256_mul_epu32(iT,b7));dB=_mm256_add_epi64(dB,_mm256_mul_epu32(hw,b7));cF=_mm256_add_epi64(cF,dA);cG=_mm256_add_epi64(cG,dB);return aN(dV(cF,cG,bc,ad),G);}inline P hT(D*f,const D*g,ap lm,const dm*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,gV(f+i,g+i,_mm256_set1_epi32(RR),Fx,bc,ad,G));RR=bN(RR,al->dC[__builtin_ctzll(~i)],E,o);}}inline P hR(D*const C,const D*const f,const D*const g,ap lm,const dm*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 bK=gV(f+i,g+i,_mm256_set1_epi32(RR),Fx,bc,ad,G);af(C+i,aH(W(C+i),bK,G));RR=bN(RR,al->dC[__builtin_ctzll(~i)],E,o);}}}}}}
#endif
#ifdef M1UNE_FPS_HAS_X86_SIMD
#pragma GCC pop_options
#endif
namespace aI{namespace dD{namespace internal{template<class e,class=P>struct fi:std::false_type{};template<class e>struct fi<e,std::void_t<decltype(std::integral_constant<uint32_t,e::o()>{})>>:std::true_type{};constexpr uint32_t hU(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 eO[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;eO[aV++]=p;while(x%p==0)x/=p;}if(x>1)eO[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 at=(o-1)/eO[i];while(at>0){if(at&1)w=w*aW%o;aW=aW*aW%o;at>>=1;}if(w==1){ok=false;break;}}if(ok)return g;}}constexpr int gE(uint32_t x){int C=0;while((x&1)==0){x>>=1;C++;}return C;}template<class e>struct fw{static constexpr int cA=gE(e::o()-1);std::array<e,cA+1>cr;std::array<e,cA+1>cM;std::array<e,cA>ht;std::array<e,cA>gJ;std::array<e,cA>gS;std::array<e,cA>gt;fw(){constexpr uint32_t fl=hU(e::o());for(int bx=1;bx<=cA;bx++){cr[bx]=e(fl).pow((e::o()-1)>>bx);cM[bx]=cr[bx].inv();}e bK=1;e ee=1;for(int i=0;i+1<cA;i++){ht[i]=cr[i+2]*bK;gJ[i]=cM[i+2]*ee;bK*=cM[i+2];ee*=cr[i+2];}bK=1;ee=1;for(int i=0;i+2<cA;i++){gS[i]=cr[i+3]*bK;gt[i]=cM[i+3]*ee;bK*=cM[i+3];ee*=cr[i+3];}}};template<class e>const fw<e>&iE(){static const fw<e>db;return db;}template<class e>P dg(F<e>&a,H iJ,H iD=true){const int n=int(a.size());assert(n>0&&(n&(n-1))==0);assert((e::o()-1)%uint32_t(n)==0);const auto&db=iE<e>();const int cf=gE(uint32_t(n));if(!iJ){int au=0;while(au<cf){if(cf-au==1){const int aC=1<<(cf-au-1);e aZ=1;for(int V=0;V<(1<<au);V++){const int ab=V<<(cf-au);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<<au))aZ*=db.ht[__builtin_ctz(~uint32_t(V))];}au++;continue;}const int aC=1<<(cf-au-2);e aZ=1;const e iC=db.cr[2];for(int V=0;V<(1<<au);V++){const e en=aZ*aZ;const e fz=en*aZ;const int ab=V<<(cf-au);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 hf=uint64_t(e(a1+cq-a3).val())*iC.val();const uint64_t gR=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+gR+hf);a[ab+i+3*aC]=e(a0+gR+cq-hf);}if(V+1!=(1<<au))aZ*=db.gS[__builtin_ctz(~uint32_t(V))];}au+=2;}}else{int au=cf;while(au>0){if(au==1){const int aC=1<<(cf-au);e aZ=1;for(int V=0;V<(1<<(au-1));V++){const int ab=V<<(cf-au+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<<(au-1)))aZ*=db.gJ[__builtin_ctz(~uint32_t(V))];}au--;continue;}const int aC=1<<(cf-au);e aZ=1;const e ic=db.cM[2];for(int V=0;V<(1<<(au-2));V++){const e en=aZ*aZ;const e fz=en*aZ;const int ab=V<<(cf-au+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 hg=uint64_t(e((e::o()+a2-a3)*ic.val()).val());a[ab+i]=e(a0+a1+a2+a3);a[ab+i+aC]=e((a0+e::o()-a1+hg)*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()-hg)*fz.val());}if(V+1!=(1<<(au-2)))aZ*=db.gt[__builtin_ctz(~uint32_t(V))];}au-=2;}if(iD){const e eM=e(n).inv();for(e&w:a)w*=eM;}}}
#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>hS(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 cS=&a==&b;auto*bG=static_cast<uint32_t*>(::operator new[](sizeof(uint32_t)*n,std::align_val_t(32)));auto*cl=cS?bG:static_cast<uint32_t*>(::operator new[](sizeof(uint32_t)*n,std::align_val_t(32)));if constexpr(std::is_same_v<e,ch::R<998244353>>){static_assert(sizeof(e)==sizeof(uint32_t)&&std::is_trivially_copyable_v<e>);std::memcpy(bG,a.data(),sizeof(uint32_t)*a.size());if(!cS)std::memcpy(cl,b.data(),sizeof(uint32_t)*b.size());}else{for(int i=0;i<int(a.size());i++)bG[i]=a[i].val();if(!cS)for(int i=0;i<int(b.size());i++)cl[i]=b[i].val();}std::memset(bG+a.size(),0,sizeof(uint32_t)*(n-a.size()));if(!cS)std::memset(cl+b.size(),0,sizeof(uint32_t)*(n-b.size()));static constexpr cy::dm cQ(998244353);const std::size_t cN=std::size_t(n)>>3;cy::fv(reinterpret_cast<__m256i*>(bG),cN,&cQ);if(!cS)cy::fv(reinterpret_cast<__m256i*>(cl),cN,&cQ);cy::hT(reinterpret_cast<__m256i*>(bG),reinterpret_cast<const __m256i*>(cl),cN,&cQ);cy::gT<true>(reinterpret_cast<__m256i*>(bG),cN,&cQ);F<e>C(bf);for(int j=0;j<bf;j++)C[j]=e::ct(bG[j]);::operator delete[](bG,std::align_val_t(32));if(!cS)::operator delete[](cl,std::align_val_t(32));return C;}
#pragma GCC pop_options
#endif
}template<class e>F<e>ib(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>gA(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::hS(a,b);}
#endif
const H cS=&a==&b;F<e>fa(n);std::copy(a.begin(),a.end(),fa.begin());internal::dg(fa,false);const e eM=e(n).inv();if(cS){for(int i=0;i<n;i++)fa[i]*=fa[i]*eM;}else{F<e>fb(n);std::copy(b.begin(),b.end(),fb.begin());internal::dg(fb,false);for(int i=0;i<n;i++)fa[i]*=fb[i]*eM;}internal::dg(fa,true,false);fa.resize(bf);return fa;}namespace internal{template<class e>F<e>hO(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 dr=int((a.size()+bo-1)/bo);const int ds=int((b.size()+bo-1)/bo);auto ed=[&](const F<e>&aB,int eh){F<F<e>>dw;dw.reserve(eh);for(int V=0;V<eh;V++){const int begin=V*bo;const int aV=std::min(bo,int(aB.size())-begin);F<e>cw(an);std::copy_n(aB.begin()+begin,aV,cw.begin());dg(cw,false);dw.emplace_back(std::move(cw));}return dw;};F<F<e>>bG=ed(a,dr);F<F<e>>cl=ed(b,ds);const int bf=int(a.size()+b.size()-1);F<e>C(bf);F<e>bv(an);for(int bJ=0;bJ<dr+ds-1;bJ++){std::fill(bv.begin(),bv.end(),e(0));const int fC=std::max(0,bJ-(ds-1));const int fF=std::min(dr-1,bJ);for(int cB=fC;cB<=fF;cB++){const int fB=bJ-cB;for(int i=0;i<an;i++)bv[i]+=bG[cB][i]*cl[fB][i];}dg(bv,true);const int dQ=bJ*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*cg;public:explicit bm(std::size_t ci):cg(static_cast<uint32_t*>(::operator new[](sizeof(uint32_t)*ci,std::align_val_t(32)))){}bm(const bm&)=delete;bm&operator=(const bm&)=delete;bm(bm&&dX)noexcept:cg(dX.cg){dX.cg=nullptr;}bm&operator=(bm&&dX)noexcept{if(this==&dX)return*this;::operator delete[](cg,std::align_val_t(32));cg=dX.cg;dX.cg=nullptr;return*this;}~bm(){::operator delete[](cg,std::align_val_t(32));}uint32_t*data(){return cg;}const uint32_t*data()const{return cg;}};template<class e>__attribute__((target("avx2,bmi"),hot))F<e>hP(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 dr=int((a.size()+bo-1)/bo);const int ds=int((b.size()+bo-1)/bo);static constexpr cy::dm cQ(998244353);const std::size_t cN=std::size_t(an)/8;auto ed=[&](const F<e>&aB,int eh){F<bm>dw;dw.reserve(eh);for(int V=0;V<eh;V++){const int begin=V*bo;const int aV=std::min(bo,int(aB.size())-begin);bm cw(an);if constexpr(std::is_same_v<e,ch::R<998244353>>){static_assert(sizeof(e)==sizeof(uint32_t)&&std::is_trivially_copyable_v<e>);std::memcpy(cw.data(),aB.data()+begin,sizeof(uint32_t)*aV);}else{for(int i=0;i<aV;i++)cw.data()[i]=aB[begin+i].val();}std::memset(cw.data()+aV,0,sizeof(uint32_t)*(an-aV));cy::fv(reinterpret_cast<__m256i*>(cw.data()),cN,&cQ);dw.emplace_back(std::move(cw));}return dw;};F<bm>bG=ed(a,dr);F<bm>cl=ed(b,ds);const int bf=int(a.size()+b.size()-1);F<e>C(bf);bm bv(an);for(int bJ=0;bJ<dr+ds-1;bJ++){std::memset(bv.data(),0,sizeof(uint32_t)*an);const int fC=std::max(0,bJ-(ds-1));const int fF=std::min(dr-1,bJ);for(int cB=fC;cB<=fF;cB++){const int fB=bJ-cB;cy::hR(reinterpret_cast<__m256i*>(bv.data()),reinterpret_cast<const __m256i*>(bG[cB].data()),reinterpret_cast<const __m256i*>(cl[fB].data()),cN,&cQ);}cy::gT<true>(reinterpret_cast<__m256i*>(bv.data()),cN,&cQ);const int dQ=bJ*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>hQ(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 hP(a,b,an);
#endif
return hO(a,b,an);}}template<class e>F<e>gO(const F<e>&a,const F<e>&b){if(a.empty()||b.empty())return{};if(std::min(a.size(),b.size())<=32)return ib(a,b);const int bf=int(a.size()+b.size()-1);int n=1;while(n<bf)n<<=1;if constexpr(internal::fi<e>::value){if constexpr(e::o()==998244353){if(n>(1<<23))return internal::hQ(a,b);}if((e::o()-1)%uint32_t(n)==0)return gA(a,b);}using dW=ch::R<167772161>;using cn=ch::R<469762049>;using bL=ch::R<754974721>;assert(n<=(1<<24));[[maybe_unused]]const unsigned __int128 ia=static_cast<unsigned __int128>(std::min(a.size(),b.size()))*(e::o()-1)*(e::o()-1);[[maybe_unused]]const unsigned __int128 iv=static_cast<unsigned __int128>(dW::o())*cn::o()*bL::o();assert(ia<iv);auto fd=[&]<class eL>(){F<eL>gM(a.size());F<eL>gN(b.size());for(int i=0;i<int(a.size());i++)gM[i]=eL(a[i].val());for(int i=0;i<int(b.size());i++)gN[i]=eL(b[i].val());return gA(gM,gN);};F<dW>c1=fd.template operator()<dW>();F<cn>c2=fd.template operator()<cn>();F<bL>c3=fd.template operator()<bL>();static const uint64_t ie=cn(dW::o()).inv().val();static const uint64_t gW=dW::o()%bL::o();static const uint64_t il=gW*(cn::o()%bL::o())%bL::o();static const uint64_t hW=bL(uint32_t(il)).inv().val();const uint64_t cO=e::o();const uint64_t gQ=dW::o()%cO;const uint64_t ih=gQ*(cn::o()%cO)%cO;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()*ie%cn::o();const uint64_t in=(r1%bL::o()+gW*(ah%bL::o()))%bL::o();const uint64_t ao=(r3+bL::o()-in)%bL::o()*hW%bL::o();uint64_t w=r1%cO;w=(w+gQ*(ah%cO))%cO;w=(w+ih*(ao%cO))%cO;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 ch{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 gX(uint64_t aW,uint64_t at,uint64_t o){uint64_t C=1;while(at>0){if(at&1)C=eg(C,aW,o);aW=eg(aW,aW,o);at>>=1;}return C;}inline uint64_t gD(){static uint64_t hs=0x123456789abcdef0ULL;hs+=0x9e3779b97f4a7c15ULL;uint64_t w=hs;w=(w^(w>>30))*0xbf58476d1ce4e5b9ULL;w=(w^(w>>27))*0x94d049bb133111ebULL;return w^(w>>31);}}inline H iH(uint64_t w){if(w<2)return false;for(uint64_t da:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}){if(w%da==0)return w==da;}uint64_t cR=w-1;int gK=0;while((cR&1)==0){cR>>=1;gK++;}for(uint64_t aW:{2ULL,325ULL,9375ULL,28178ULL,450775ULL,9780504ULL,1795265022ULL}){if(aW%w==0)continue;uint64_t x=internal::gX(aW%w,cR,w);if(x==1||x==w-1)continue;H gU=true;for(int i=1;i<gK;i++){x=internal::eg(x,x,w);if(x==w-1){gU=false;break;}}if(gU)return false;}return true;}namespace internal{inline uint64_t iy(uint64_t w){for(uint64_t da:{2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL}){if(w%da==0)return da;}while(true){const uint64_t iG=gD()%(w-1)+1;uint64_t y=gD()%(w-1)+1;uint64_t x=0;uint64_t dT=0;uint64_t df=1;uint64_t eD=1;auto fA=[&](uint64_t gZ){return static_cast<uint64_t>((static_cast<unsigned __int128>(eg(gZ,gZ,w))+iG)%w);};while(df==1){x=y;for(uint64_t i=0;i<eD;i++)y=fA(y);for(uint64_t ab=0;ab<eD&&df==1;ab+=128){dT=y;uint64_t bK=1;const uint64_t V=std::min<uint64_t>(128,eD-ab);for(uint64_t i=0;i<V;i++){y=fA(y);const uint64_t ft=x>y?x-y:y-x;bK=eg(bK,ft,w);}df=std::gcd(bK,w);}eD<<=1;}if(df==w){do{dT=fA(dT);const uint64_t ft=x>dT?x-dT:dT-x;df=std::gcd(ft,w);}while(df==1);}if(df!=w)return df;}}inline P fh(uint64_t w,F<uint64_t>&dv){if(w==1)return;if(iH(w)){dv.push_back(w);return;}const uint64_t ha=iy(w);fh(ha,dv);fh(w/ha,dv);}}inline F<uint64_t>io(uint64_t w){assert(w>=1);F<uint64_t>C;internal::fh(w,C);std::sort(C.begin(),C.end());return C;}inline F<std::pair<uint64_t,int>>ef(uint64_t w){F<uint64_t>dv=io(w);F<std::pair<uint64_t,int>>C;for(uint64_t da:dv){if(C.empty()||C.back().first!=da){C.emplace_back(da,1);}else{C.back().second++;}}return C;}inline F<uint64_t>eO(uint64_t w){F<uint64_t>C={1};for(const auto&cD:ef(w)){const int iq=int(C.size());uint64_t bU=1;for(int at=1;at<=cD.second;at++){bU*=cD.first;for(int i=0;i<iq;i++){C.push_back(C[i]*bU);}}}std::sort(C.begin(),C.end());return C;}inline uint64_t iB(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 jy(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 ch{inline H hZ(uint64_t o){if(o==2||o==4)return true;if(o<2)return false;uint64_t cR=o;if((cR&1)==0){cR>>=1;if((cR&1)==0)return false;}return ef(cR).size()==1;}inline uint64_t fl(uint64_t o){assert(o>=2);if(o==2)return 1;if(!hZ(o))return 0;const uint64_t hB=iB(o);const F<std::pair<uint64_t,int>>dv=ef(hB);for(uint64_t ej=2;ej<o;ej++){if(std::gcd(ej,o)!=1)continue;H dS=true;for(const auto&cD:dv){if(internal::gX(ej,hB/cD.first,o)==1){dS=false;break;}}if(dS)return ej;}return 0;}}}namespace aI{namespace ch{namespace internal{template<class T>struct bt{using dp=T;static constexpr int cY=0;};template<class T,class iA>struct bt<F<T,iA>>{using dp=typename bt<T>::dp;static constexpr int cY=bt<T>::cY+1;};template<class ak>P fg(const ak&aB,F<int>&aP){if constexpr(bt<ak>::cY>0){assert(!aB.empty());assert(aB.size()<=std::size_t(std::numeric_limits<int>::max()));aP.push_back(int(aB.size()));fg(aB.front(),aP);}}template<class ak,class e>P fe(const ak&aB,const F<int>&aP,int bx,F<e>&cz){if constexpr(bt<ak>::cY==0){cz.push_back(aB);}else{assert(bx<int(aP.size()));assert(int(aB.size())==aP[bx]);for(const auto&fJ:aB){fe(fJ,aP,bx+1,cz);}}}template<class ak,class e>P gq(ak&aB,const F<int>&aP,int bx,const F<e>&cz,int&cd){if constexpr(bt<ak>::cY==0){assert(cd<int(cz.size()));aB=cz[cd++];}else{assert(bx<int(aP.size()));aB.resize(aP[bx]);for(auto&fJ:aB){gq(fJ,aP,bx+1,cz,cd);}}}template<class ak>F<int>go(const ak&ah,const ak&ao,F<typename bt<ak>::dp>&dl,F<typename bt<ak>::dp>&dk){F<int>aP;fg(ah,aP);assert(int(aP.size())==bt<ak>::cY);F<int>gL;fg(ao,gL);assert(gL==aP);fe(ah,aP,0,dl);fe(ao,aP,0,dk);std::reverse(aP.begin(),aP.end());return aP;}template<class ak>ak gp(F<int>ar,const F<typename bt<ak>::dp>&cz){std::reverse(ar.begin(),ar.end());ak C;int cd=0;gq(C,ar,0,cz,cd);assert(cd==int(cz.size()));return C;}inline int ey(const F<int>&ar){int64_t aV=1;for(int aA:ar){assert(aA>0);aV*=aA;assert(aV<=std::numeric_limits<int>::max());}return int(aV);}inline F<int>hY(const F<int>&ar){const int bF=int(ar.size());const int aU=ey(ar);F<int>dy(aU);if(bF==0)return dy;for(int bM=0;bM<aU;bM++){int hE=0;int aO=1;for(int aE=0;aE+1<bF;aE++){aO*=ar[aE];hE+=bM/aO;}dy[bM]=hE%bF;}return dy;}template<class e>F<e>ff(const F<e>&fu,e ratio){const int ci=int(fu.size());if(ci<=64){F<e>C(ci);e hq=1;for(int i=0;i<ci;i++){e bU=1;for(const e&iu:fu){C[i]+=iu*bU;bU*=hq;}hq*=ratio;}return C;}auto gx=[](e aW,int cV){F<e>C(cV);if(cV==0)return C;C[0]=1;e bU=1;for(int i=0;i+1<cV;i++){C[i+1]=C[i]*bU;bU*=aW;}return C;};F<e>iI=gx(ratio,2*ci-1);F<e>bw=gx(ratio.inv(),ci);F<e>eS(fu);for(int i=0;i<ci;i++)eS[i]*=bw[i];std::reverse(eS.begin(),eS.end());F<e>bK=dD::gO(eS,iI);F<e>C(ci);for(int i=0;i<ci;i++)C[i]=bK[ci-1+i]*bw[i];return C;}}template<class e>F<e>gn(const F<int>&ar,const F<e>&ah,const F<e>&ao){static_assert(dD::internal::fi<e>::value,"truncated multivariate convolution requires a static-modulus type");const int bF=int(ar.size());const int aU=internal::ey(ar);assert(int(ah.size())==aU);assert(int(ao.size())==aU);if(bF==0)return{ah[0]*ao[0]};int64_t eA=1;while(eA<2LL*aU-1)eA<<=1;assert(eA<=std::numeric_limits<int>::max());const int an=int(eA);assert((e::o()-1)%uint32_t(an)==0);const F<int>dy=internal::hY(ar);F<F<e>>bY(bF,F<e>(an));F<F<e>>dj(bF,F<e>(an));for(int i=0;i<aU;i++){bY[dy[i]][i]=ah[i];dj[dy[i]][i]=ao[i];}for(int cZ=0;cZ<bF;cZ++){dD::internal::dg(bY[cZ],false);dD::internal::dg(dj[cZ],false);}F<F<e>>bv(bF,F<e>(an));for(int cp=0;cp<bF;cp++){for(int co=0;co<bF;co++){F<e>&iw=bv[(cp+co)%bF];const F<e>&ix=bY[cp];const F<e>&it=dj[co];for(int i=0;i<an;i++){iw[i]+=ix[i]*it[i];}}}for(int cZ=0;cZ<bF;cZ++){dD::internal::dg(bv[cZ],true);}F<e>C(aU);for(int i=0;i<aU;i++){C[i]=bv[dy[i]][i];}return C;}template<class ak,std::enable_if_t<(internal::bt<ak>::cY>0),int> =0>ak gn(const ak&ah,const ak&ao){using e=typename internal::bt<ak>::dp;F<e>dl,dk;F<int>ar=internal::go(ah,ao,dl,dk);F<e>fk=gn(ar,dl,dk);return internal::gp<ak>(std::move(ar),fk);}template<class e>F<e>ex(const F<int>&ar,const F<e>&ah,const F<e>&ao){const int aU=internal::ey(ar);assert(int(ah.size())==aU);assert(int(ao.size())==aU);if(ar.empty())return{ah[0]*ao[0]};const uint32_t cC=e::o();H gG=true;for(int aA:ar){if((cC-1)%uint32_t(aA)!=0)gG=false;}if(!gG){F<int>bE;for(int aA:ar){if(aA!=1)bE.push_back(aA);}if(bE.empty())return{ah[0]*ao[0]};F<int>dP(bE.size());for(int i=0;i<int(bE.size());i++){const int64_t he=2LL*bE[i]-1;assert(he<=std::numeric_limits<int>::max());dP[i]=int(he);}const int eG=internal::ey(dP);int64_t ez=0;int64_t fm=1;for(int aE=0;aE<int(bE.size());aE++){ez+=int64_t(bE[aE]-1)*fm;fm*=dP[aE];}assert(fm==eG);assert(2*ez+1==eG);assert(ez<std::numeric_limits<int>::max());const int gr=int(ez)+1;F<e>gI(gr);F<e>gF(gr);for(int bM=0;bM<aU;bM++){int cb=bM;int cL=0;int gy=1;for(int aE=0;aE<int(bE.size());aE++){const int fs=cb%bE[aE];cb/=bE[aE];cL+=fs*gy;gy*=dP[aE];}gI[cL]=ah[bM];gF[cL]=ao[bM];}F<e>gB=dD::gO(gI,gF);assert(int(gB.size())==eG);F<e>C(aU);for(int cL=0;cL<eG;cL++){int cb=cL;int bM=0;int aO=1;for(int aE=0;aE<int(bE.size());aE++){const int fs=cb%dP[aE];cb/=dP[aE];bM+=(fs%bE[aE])*aO;aO*=bE[aE];}C[bM]+=gB[cL];}return C;}const uint64_t dS=fl(cC);assert(dS!=0);F<e>bY(ah);F<e>dj(ao);int aO=1;for(int aA:ar){assert((cC-1)%uint32_t(aA)==0);const e cr=e(dS).pow((cC-1)/aA);for(int V=0;V<aU;V+=aO*aA){for(int ab=0;ab<aO;ab++){F<e>eJ(aA);F<e>eH(aA);for(int i=0;i<aA;i++){eJ[i]=bY[V+ab+aO*i];eH[i]=dj[V+ab+aO*i];}eJ=internal::ff(eJ,cr);eH=internal::ff(eH,cr);for(int i=0;i<aA;i++){bY[V+ab+aO*i]=eJ[i];dj[V+ab+aO*i]=eH[i];}}}aO*=aA;}for(int i=0;i<aU;i++){bY[i]*=dj[i];}aO=1;for(int aA:ar){const e cM=e(dS).pow((cC-1)/aA).inv();for(int V=0;V<aU;V+=aO*aA){for(int ab=0;ab<aO;ab++){F<e>eV(aA);for(int i=0;i<aA;i++){eV[i]=bY[V+ab+aO*i];}eV=internal::ff(eV,cM);for(int i=0;i<aA;i++){bY[V+ab+aO*i]=eV[i];}}}aO*=aA;}const e ir=e(aU).inv();for(e&w:bY)w*=ir;return bY;}template<class ak,std::enable_if_t<(internal::bt<ak>::cY>0),int> =0>ak ex(const ak&ah,const ak&ao){using e=typename internal::bt<ak>::dp;F<e>dl,dk;F<int>ar=internal::go(ah,ao,dl,dk);F<e>fk=ex(ar,dl,dk);return internal::gp<ak>(std::move(ar),fk);}}}using eq=aI::ch::ij;P iQ(){ll X,Y,Z;fV(X,Y,Z);vv(string,A,Z,Y);vv(string,B,Z,Y);FOR(z,Z)FOR(y,Y){fV(A[z][y]);}FOR(z,Z)FOR(y,Y){fV(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::ch::ex(A_black,inv_B_white);auto C2=aI::ch::ex(A_white,inv_B_black);ll hv=bj<ll>;FOR(z,Z)FOR(y,Y)FOR(x,X){eq c=C1[z][y][x]+C2[z][y][x];iN(hv,c.val());}fL(hv);}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--)iQ();return 0;}