#include #include namespace my{ void main(); void solve(); } int main(){my::main();} namespace my{ #define eb emplace_back #define FO(n) for(ll ij=n;ij--;) #define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i>(istream&i,ulll&x){ull t;i>>t;x=t;return i;} ostream&operator<<(ostream&o,const ulll&x){return(x<10?o:o<>(istream&i,lll&x){ll t;i>>t;x=t;return i;} ostream&operator<<(ostream&o,const lll&x){return o<0?x:-x);} auto range(bool s,ll a,ll b=1e18,ll c=1){if(b==1e18)b=a,(s?b:a)=0;return array{a-s,b,c};} constexpr char nl=10; constexpr char sp=32; lll pw(lll x,ll n,ll m=0){assert(n>=0);lll r=1;while(n)n&1?r*=x:r,x*=x,m?r%=m,x%=m:r,n>>=1;return r;} templateconcept vectorial=is_base_of_v,V>; templateistream&operator>>(istream&i,vector&v){fe(v,e)i>>e;return i;} templateostream&operator<<(ostream&o,const vector&v){fe(v,e)o<?nl:sp);return o;} templatestruct vec:vector{ using vector::vector; vec(const vector&v){vector::operator=(v);} vec&operator+=(const vec&u){vec&v=*this;fo(i,v.size())v[i]+=u[i];return v;} vec&operator-=(const vec&u){vec&v=*this;fo(i,v.size())v[i]-=u[i];return v;} vec&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;} vec operator+(const vec&u)const{return vec{*this}+=u;} vec operator-(const vec&u)const{return vec{*this}-=u;} vec operator^(const vec&u)const{return vec{*this}^=u;} vec&operator++(){fe(*this,e)++e;return*this;} vec&operator--(){fe(*this,e)--e;return*this;} vec operator-()const{vec v=*this;fe(v,e)e=-e;return v;} }; void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<>...>>a);} auto sinen(const string&b="a"){string s;lin(s);vecr;fe(s,e)r.eb(b.size()==1?e-b[0]:b.find_first_of(e));return r;} auto sinen(ll n,const string&b="a"){vec>r;fo(n)r.eb(sinen(b));return r;} templatevoid pp(const auto&...a){ll n=sizeof...(a);((cout<0,c)),...);cout<=2)M+=t.end()[-2]*10; pp(pw(N,M,10)); }}