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