#include <iostream>
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <bitset>
#include <sstream>
#include <deque>
#include <cassert>
#include <functional>
/*
#if __has_include(<atcoder/modint>)
#   include <atcoder/modint>
#   include <atcoder/segtree>
#   include <atcoder/dsu>
#   include <atcoder/math>
#   include <atcoder/scc>
#endif
*/
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <ios>
#include <iomanip>
#include <cstdio>
#if __has_include( <boost/integer/extended_euclidean.hpp>)
#   include <boost/multiprecision/cpp_int.hpp>
#   include<boost/integer/extended_euclidean.hpp>
#endif
#define CLiBCXX_DEBUG
#define ll long long
#define ull unsigned long long
#define hmap unordered_map
#define hset unordered_set
using namespace std;
#if __has_include(<atcoder/modint>)
    using namespace atcoder;
    using mint10 = static_modint<10>;
    using mint24 = static_modint<24>;
    using mint3 = static_modint<3>;
    using minta = modint998244353;
    using mintb = modint1000000007;
#endif



ll powll(ll a, ll b)
{
    return (ll)pow(a, b / 2) * (ll)pow(a, b - b / 2);
}
ll sum(ll a, ll b)
{
    return a + b;
}
ll e()
{
    return 0;
}

//see abc126 b
ll lis(vector<ll> v){
    ll dp[200300];
    ll sz = v.size();
    for(ll i = 0; i < sz; ++i){
        dp[i]=LLONG_MAX;
    }
    auto itr = v.begin();
    auto len = 1;
    dp[0]=*itr;
    ++itr;
    for(;itr != v.end();++itr){
        ll val = *itr;
        ll l = -1;
        ll r = len;
        while(r - l!=1){
            ll piv = (l+r)/2;
            if(dp[piv]>=val){
                r = piv;
            }else{
                l = piv;
            }
        }
        if(dp[r]==LLONG_MAX){
            len++;
        }
        dp[r]=val;
    }
    return len;
}

//return true if an argument is prime or one
#if __has_include( <boost/integer/extended_euclidean.hpp>)
bool isPrime(double num, set<ll>& primes, set<ll>& comps){
    if(num==1){
        return false;
    }
    if(primes.find(num)!=primes.end()){
        return true;
    }
    if(comps.find(num)!=comps.end()){
        return false;
    }
    double sq = sqrtf64(num);
    for(int32_t i = 2; i <= sq; ++i){
        if((ll)num%i==0){
            comps.insert(num);
            return false;
        }
    }
    primes.insert(num);
    return true;
}
#endif
//up to 3000 charactors
string LCS(string s, string t){
    ll ss = s.size();
    ll ts = t.size();
    ll **a = new ll*[3001];
    for(ll i = 0; i < 3001; ++i) a[i]= new ll[3001];
    for(ll i = 0; i < 3001; ++i){
        a[i][0]=0;
    }
    for(ll j = 0; j < 3001; ++j){
        a[0][j]=0;
    }
    for(ll i = 1; i <= ss; ++i){
        for(ll j = 1; j <= ts; ++j){
            if(s[i-1]==t[j-1]){
                a[i][j]=a[i-1][j-1]+1;
            }else{
                a[i][j]=max(a[i-1][j],a[i][j-1]);
            }
        }
    }
    //cout << a[ss][ts]<<endl; // test
    vector<char> rans;
    ll i_r = ss;
    ll j_r = ts;
    while(a[i_r][j_r]!=0){
        if(s[i_r-1]==t[j_r-1]){
            rans.push_back(s[i_r-1]);
            i_r--;
            j_r--;
        }else{
            if(a[i_r][j_r]==a[i_r-1][j_r]){
                i_r--;
            }else{
                j_r--;
            }
        }
    }
    stringstream sst;
    for(auto i = rans.rbegin(); i != rans.rend(); ++i){
        sst << *i;
    }
    for(ll i = 0; i < 3001; ++i) delete[] a[i];
    delete[] a;
    return sst.str();
}

ll zeroll(){
    return 0;
}
#if __has_include(<atcoder/modint>)
ll count_inversion(vector<ll> v)
{
    ll n = v.size();
    segtree<ll, sum,zeroll> seg(n);
    ll c = 0;
    for(ll i = 0; i < n; ++i){
        ll tmpa=v[i];
        tmpa--;
        c+=seg.prod(tmpa,n);
        seg.set(tmpa,1);
    }
    return c;
}
#endif

//TODO パッケージ化
/*
ll root(ll v,vector<ll>& parents){
    assert(parents.size()>v&&v>=0);
    if(parents[v]==v){
        return v;
    }
    return parents[v]=root(parents[v], parents);
}
//最小全域木
vector<vector<ll>> MST(vector<ll> starts, vector<ll> ends, vector<ll> costs, ll n){
    assert(starts.size()==ends.size());
    assert(starts.size()==costs.size());
    ll m = starts.size();
    for(ll i = 0; i < m; ++i){
        assert(starts[i]!=ends[i]);
    }
    set<ll> added;
    auto more = [](pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b){
        return a.first>b.first;
    };
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,decltype(more)> pq(more); 
    for(ll i = 0; i < m; ++i){
        pq.push(make_pair(costs[i],make_pair(starts[i],ends[i])));
    }
    vector<ll> tmpv;
    vector<vector<ll>> ans(n,tmpv);
    vector<ll> parents(n);
    for(ll i = 0; i < n; ++i){
        parents[i]=i;
    }
    vector<ll> tree_size(n,1);
    auto marge_sec = [](ll a, ll b, vector<ll>& parents, vector<ll>& tree_size){
        assert(a!=b);
        tree_size[root(a, parents)]+=tree_size[root(b, parents)];
        parents[root(b,parents)]=root(a, parents);
    };
    ll total_cost = 0;
    while(tree_size[parents[0]]!=n&&!pq.empty()){
        auto current = pq.top();
        auto cost = current.first;
        auto edge = current.second;
        ll a = edge.first;
        ll b = edge.second;
        pq.pop();
        if(root(a,parents)==root(b,parents)){
            //skip because it makes a cycle
        }else{
            marge_sec(a,b,parents,tree_size);
            ans[a].push_back(b);
            total_cost+=cost;
        }
    }
    return ans;
}

//最小全域木のコスト合計
ll MSTCost(vector<ll> starts, vector<ll> ends, vector<ll> costs, ll n){
    assert(starts.size()==ends.size());
    assert(starts.size()==costs.size());
    ll m = starts.size();
    for(ll i = 0; i < m; ++i){
        assert(starts[i]!=ends[i]);
    }
    set<ll> added;
    auto more = [](pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b){
        return a.first>b.first;
    };
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,decltype(more)> pq(more); 
    for(ll i = 0; i < m; ++i){
        pq.push(make_pair(costs[i],make_pair(starts[i],ends[i])));
    }
    vector<ll> tmpv;
    vector<vector<ll>> ans(n,tmpv);
    vector<ll> parents(n);
    for(ll i = 0; i < n; ++i){
        parents[i]=i;
    }
    vector<ll> tree_size(n,1);
    auto marge_sec = [](ll a, ll b, vector<ll>& parents, vector<ll>& tree_size){
        assert(a!=b);
        tree_size[root(a, parents)]+=tree_size[root(b, parents)];
        parents[root(b,parents)]=root(a, parents);
    };
    ll total_cost = 0;
    while(tree_size[parents[0]]!=n&&!pq.empty()){
        auto current = pq.top();
        auto cost = current.first;
        auto edge = current.second;
        ll a = edge.first;
        ll b = edge.second;
        pq.pop();
        if(root(a,parents)==root(b,parents)){
            //skip because it makes a cycle
        }else{
            marge_sec(a,b,parents,tree_size);
            ans[a].push_back(b);
            total_cost+=cost;
        }
    }
    return total_cost;
}
*/

#if __has_include(<atcoder/all>)
//二点間最短経路 大体O((N+M)logM)
ll shortestPathDistance(ll size, vector<ll> froms, vector<ll> tos, vector<ll> costs, int start, int end){
    assert(froms.size()==tos.size());
    assert(froms.size()==costs.size());
    mcf_graph<int,ll> g(size);
    for(ll i = 0; i < froms.size(); ++i){
        g.add_edge(froms[i],tos[i],1,costs[i]);
    }
    auto p = g.flow(start,end);
    return (p.first!=0?p.second:LLONG_MAX);
}

//二点間最短経路 コストが1の場合
ll shortestPathDistance(ll size, vector<ll> froms, vector<ll> tos, int start, int end){
    assert(froms.size()==tos.size());
    vector<ll> costs;
    for(ll i = 0; i < froms.size(); ++i){
        costs.push_back(1);
    }
    return shortestPathDistance(size,froms,tos,costs,start,end);
}
#endif

//ダイクストラ　始点固定
vector<ll> shortestPathDistances(ll size, vector<vector<pair<ll,ll>>> edges, ll start){
    #define iNF LLONG_MAX/3
    vector<ll> ans(size,iNF);
    ans[start] = 0;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> nexts;
    nexts.push(make_pair(0,start));
    vector<ll> determined(size,false);
    while(!nexts.empty()){
        ll idx = nexts.top().second;
        ll cost = nexts.top().first;
        nexts.pop();
        if(determined[idx]){
            continue;
        }
        determined[idx]=true;
        for(ll i = 0; i < edges[idx].size(); ++i){
            if(!determined[edges[idx][i].first]){
                if(ans[edges[idx][i].first]>ans[idx]+edges[idx][i].second){
                    nexts.push(make_pair(ans[idx]+edges[idx][i].second,edges[idx][i].first));
                    ans[edges[idx][i].first]=ans[idx]+edges[idx][i].second;
                }
            }
        }
    }
    return ans;
}

//葉が始点群、根が終点
template<class Score>
class TreeDP{
    private:
    vector<Score> score;
    function<Score (Score, Score)> op;
    vector<vector<int>> edges;
    int size;
    public:
    TreeDP(int n, Score def, function<Score (Score, Score)> op){
        vector<int> score(n,def);
        this.score=score;
        this.op = op;
        this.size = n;
    }
    void add_edge(int a, int b){
        edges[a].push_back(b);
    }
    vector<Score> prod(){
        vector<int> in(size,0);//入向辺
        for(int i = 0; i < edges.size(); ++i){
            for(int j = 0; j < edges[i].size(); ++j){
                in[edges[i][j]]++;
            }
        }
        queue<int> no_in;
        for(int i = 0; i < in.size(); ++i){
            if(in[i]==0){
                no_in.push(i);
            }
        }
        vector<int> sorted;
        while(!no_in.empty()){
            int curr = no_in.front();
            sorted.push_back(curr);
            no_in.pop();
            for(ll i = 0; i < edges[curr].size(); ++i){
                int to = edges[curr][i];
                in[to]--;
                if(in[to]==0){
                    no_in.push(to);
                }
            }
        }
        for(int i = 0; i < sorted.size(); ++i){
            for(int j = 0; j < edges[sorted[i]].size(); ++j){
                int to = edges[sorted[i]][j];
                int from = i;
                score[to]=op(score[to],score[from]);
            }
        }
        return score;
    }
};
namespace cell{
    //Union-Find
    class uf{
        public:
        uf(ll n){
            par.resize(n);
            sizes.resize(n);
            for(ll i = 0; i < n; ++i){
                par[i]=i;
                sizes[i]=1;
            }
        }
        void merge(ll a, ll b){
            sizes[root(a)]+=sizes[root(b)];
            par[root(b)]=root(a);
        }
        vector<ll> par;
        vector<ll> sizes;
        ll root(ll a){
            if(par[a]==a){
                return a;
            }else{
                return par[a]=root(par[a]);
            }
        }
        ll size(ll a){
            return sizes[root(a)];
        }
        bool same(ll a, ll b){
            if(root(a)==root(b)){
                return true;
            }else{
                return false;
            }
        }
    };
    class modint998244353{
        public:
        ll m = 998244353;
        ll value;
        modint998244353(ll a){
            value = (a+m*10)%m;
        }
        modint998244353 operator*(modint998244353 b){
            return modint998244353((this->value*b.value+m)%m);
        }
        modint998244353 pow(ll b){
            if(b==1){
                return *this;
            }else if(b==0){
                return 1;
            }
            if(b%2==1){
                return pow(b-1)**this;
            }else{
                modint998244353 co = pow(b/2);
                return co*co;
            }
        }
        modint998244353 operator/(modint998244353 b){
            if(b.value==1){
                return *this;
            }
            return *this*b.pow(m-2);
        }
        modint998244353 operator+(modint998244353 b){
            return this->value+b.value;
        }
        modint998244353 operator-(modint998244353 b){
            return this->value-b.value;
        }
    };
    class modint1000000007{
        public:
        ll m = 998244353;
        ll value;
        modint1000000007(ll a){
            value = (a+m*10)%m;
        }
        modint1000000007 operator*(modint1000000007 b){
            return modint1000000007((this->value*b.value+m)%m);
        }
        modint1000000007 pow(ll b){
            if(b==1){
                return *this;
            }else if(b==0){
                return 1;
            }
            if(b%2==1){
                return pow(b-1)**this;
            }else{
                modint1000000007 co = pow(b/2);
                return co*co;
            }
        }
        modint1000000007 operator/(modint1000000007 b){
            if(b.value==1){
                return *this;
            }
            return *this*b.pow(m-2);
        }
        modint1000000007 operator+(modint1000000007 b){
            return this->value+b.value;
        }
        modint1000000007 operator-(modint1000000007 b){
            return this->value-b.value;
        }
    };
    //強連結成分分解
    class scc_graph{
        public:
        ll ns;//size
        scc_graph(ll n){
            ns=n;
            vector<vector<ll>> vn(ns);
            v = vn;
            rv = vn;
        }
        void add_edge(int s, int t){
            assert(0<=s);
            assert(s<ns);
            assert(0<=t);
            assert(t<ns);
            v[s].push_back(t);
            rv[t].push_back(s);
        }
        vector<vector<ll>> scc(){
            dfsVec.resize(0);
            checked.assign(ns,false);
            for(ll i = 0; i < ns; ++i){
                dfs(i);
            }
            vector<vector<ll>> ans;
            ll m = dfsVec.size();
            checked.assign(ns,false);
            for(ll i = m-1; i>=0; --i){
                ll el = dfsVec[i];
                rdfsVec.resize(0);
                if(checked[el]){
                    continue;
                }
                rdfs(el);
                ans.push_back(rdfsVec);
            }
            return ans;
        }
        protected:
        vector<ll> dfsVec;
        vector<ll> rdfsVec;
        void dfs(ll i){
            if(checked[i]){
                return;
            }
            checked[i]=true;
            auto elist = v[i];
            for(ll j = 0; j < elist.size(); ++j){
                dfs(elist[j]);
            }
            dfsVec.push_back(i);
        }
        void rdfs(ll i){
            if(checked[i]){
                return;
            }
            checked[i]=true;
            auto elist = rv[i];
            for(ll j = 0; j < elist.size(); ++j){
                rdfs(elist[j]);
            }
            rdfsVec.push_back(i);
        }
        vector<bool> checked;
        vector<vector<ll>> v;
        vector<vector<ll>> rv;
    };
    //セグメントツリー
    template<class S>
    class segtree{
        public:
        segtree(S n, function<S(S,S)> op, function<S()> e){
            this->op=op;
            this->e=e;
            ns = n;
            S default_val = e();
            val_con.assign(ns*2,default_val);
        }
        void set(ll p, S x){
            ll idx = p + ns;
            val_con[idx]=x;
            while(idx>0){
                idx = ((idx+1)/2)-1;
                ll l = (idx+1)*2-1;
                ll r = (idx+1)*2;
                val_con[idx]=op(val_con[l],val_con[r]);
            }
            val_con[0]=op(val_con[1],val_con[2]);
        }
        S get(ll p){
            ll idx = p + ns;
            return val_con[idx];
        }
        S prod(ll l, ll r){
            ll idx = l;
            S ans = e();
            while(idx<r){
                ll size = 1;
                ll raw_idx = idx+ns;
                while(idx+size*2-1<r&&raw_idx>0&&(raw_idx+1)%2==0){
                    size*=2;
                    raw_idx=((raw_idx+1)/2-1);
                }
                ans = op(ans,val_con[raw_idx]);
                idx+=size;
            }
            return ans;
        }
        protected:
        ll ns;
        vector<S> val_con;
        function<S(S,S)> op;
        function<S()> e;
    };
    //2次元UnionFind
    class squf:cell::uf{
        public:
        squf(ll n):cell::uf(n*n){
            sz=n;
        }
        void merge(ll a1, ll a2, ll b1, ll b2){
            cell::uf::merge(a1*sz+a2,b1*sz+b2);
        }
        bool same(ll a1, ll a2, ll b1, ll b2){
            return cell::uf::same(a1*sz+a2,b1*sz+b2);
        }
        protected:
        ll sz;
    };
    //最短経路(ダイクストラ)
    class sp_graph{
        public:
        sp_graph(ll n){
            ns = n;
            w.assign(n,inf);
            seen.assign(n,false);
            calculated=false;
            vector<pair<ll,ll>> b;
            seen_cnt=0;
            edges.assign(n,b);
            queued.assign(n,false);
            sources.resize(0);
        }
        void add_edge(ll a, ll b, ll cost){
            assert(0<=a&&a<ns);
            assert(0<=b&&b<ns);
            assert(0<=cost);
            edges[a].push_back(make_pair(b,cost));
        }
        void set_seen(ll n){
            seen[n]=true;
        }
        void set_seen(function<bool(ll)> if_set){
            for(ll i = 0; i < ns; ++i){
                if(if_set(i)){
                    set_seen(i);
                }
            }
        }
        void set_seen(function<bool(ll,void*)> if_set, void* ptr){
            for(ll i = 0; i < ns; ++i){
                if(if_set(i, ptr)){
                    set_seen(i);
                }
            }
        }
        //最短経路上の重みの総和を返します。経路が存在しない場合はLLONG_MAXと等しい値を返します。
        ll sp(ll a, ll b){
            assert(0<=a&&a<ns);
            assert(0<=b&&b<ns);
            if(calculated&&start_node==a){
                return w[b];
            }
            reset();
            start_node=a;
            end_node=b;
            calculated=true;
            //bfsで到達不能な場所を数える
            vector<bool> bfs_reachable(ns,false);
            bfs(edges,bfs_reachable,a);
            ll reachables = 0;
            for(ll i = 0; i < ns; ++i){
                if(bfs_reachable[i]){
                    reachables++;
                }
            }
            //bfs終了
            queued_cost.assign(ns,LLONG_MAX);
            sources.assign(ns,-1);
            priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;//pair<score,index>
            priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> dets;//pair<score,index>
            pq.push(make_pair(0,a));
            dets.push(make_pair(0,-1));
            while(!pq.empty()){
                auto f = pq.top();
                auto source = dets.top().second;
                pq.pop();
                dets.pop();
                ll score = f.first;
                ll idx = f.second;
                if(seen[idx]){
                    continue;
                }
                seen[idx]=true;
                sources[idx]=source;
                w[idx]=score;
                seen_cnt++;
                if(seen_cnt==reachables){
                    break;
                }
                auto list = edges[idx];
                for(ll i = 0; i < list.size();++i){
                    ll d = list[i].first;
                    ll edge_cost = list[i].second;
                    if(seen[d]){
                        continue;
                    }
                    queued[d]=true;
                    if(score+edge_cost<queued_cost[d]){
                        queued_cost[d]=score+edge_cost;
                        pq.push(make_pair(score+edge_cost,d));
                        dets.push(make_pair(score+edge_cost,idx));
                    }
                }
            }
            return w[b];
        }
        vector<ll> path(){
            assert(calculated);
            vector<ll> rans(0);
            ll b = end_node;
            ll a = start_node;
            while(true){
                if(b==-1){
                    return vector<ll>(0);
                }else if(a==b){
                    rans.push_back(b);
                    break;
                }else{
                    rans.push_back(b);
                    b=sources[b];
                }
            }
            vector<ll> ans(rans.size());
            for(ll i = 0; i < rans.size(); ++i){
                ans[i]=rans[rans.size()-i-1];
            }
            assert(ans[0]==start_node);
            return ans;
        }
        vector<ll> get_sources(){
            return sources;
        }
        protected:
        void reset(){
            calculated=false;
            seen.assign(ns,false);
            w.assign(ns,inf);
            seen_cnt=0;
            queued.assign(ns,false);
        }
        void bfs(vector<vector<pair<ll,ll>>>& edges, vector<bool>& bfs_reachable, ll a){
            assert(0<=a&&a<=ns);
            if(bfs_reachable[a]){
                return;
            }
            bfs_reachable[a]=true;
            for(ll i = 0; i < edges[a].size(); ++i){
                bfs(edges,bfs_reachable,edges[a][i].first);
            }
            return;
        }
        const ll inf=LLONG_MAX;
        ll ns;
        vector<ll> w;
        vector<bool> seen;
        vector<bool> queued;
        vector<ll> queued_cost;
        ll seen_cnt;
        ll start_node;
        ll end_node;
        vector<vector<pair<ll,ll>>> edges;
        bool calculated;
        vector<ll> sources;
    };
    class grid_sp:cell::sp_graph{
        public:
        grid_sp(ll r, ll c):cell::sp_graph(r*c){
            rs=r;
            cs=c;
        }
        void add_edge(ll x1, ll y1, ll x2, ll y2, ll cost){
            cell::sp_graph::add_edge(x1*cs+y1,x2*cs+y2,cost);
            return;
        }
        void set_seen(ll x, ll y){
            cell::sp_graph::set_seen(x*cs+y);
            return;
        }
        void set_seen(function<bool(ll,ll)> if_set){
            for(ll i = 0; i < rs; ++i){
                for(ll j = 0; j < cs; ++j){
                    if(if_set(i,j)){
                        set_seen(i,j);
                    }
                }
            }
        }
        void set_seen(function<bool(ll,ll, void*)> if_set, void* ptr){
            for(ll i = 0; i < rs; ++i){
                for(ll j = 0; j < cs; ++j){
                    if(if_set(i,j,ptr)){
                        set_seen(i,j);
                    }
                }
            }
        }
        ll sp(ll x1, ll y1, ll x2, ll y2){
            ll a = x1*cs+y1;
            ll b = x2*cs+y2;
            return cell::sp_graph::sp(a,b);
        }
        protected:
        ll rs;
        ll cs;
    };
}
struct grid_ex_sp{
    ll h,w,p;
    char* grid;
    ll size;
    grid_ex_sp(ll H, ll W, ll P, char* GRID){
        grid = GRID;
        h = H;
        w = W;
        p = P;
        calc=false;
        size = h*w*p;
    }
    bool calc;
    void sp(ll r,ll c, ll re, ll ce){
        scores.assign(size,LLONG_MAX);
        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
        for(ll i = 0; i < p; ++i){
            pq.emplace(0,idx(r,c,i));
        }
        while(!pq.empty()){
            auto tp = pq.top();
            ll score = tp.first;
            ll curr = tp.second;
            pq.pop();
            ll cur_r,cur_c,cur_p;
            tie(cur_r,cur_c,cur_p)=locs(curr);
            
        }
    }
    vector<ll> scores;
    ll idx(ll r, ll c, ll pat){
        return r*w+c+h*w*pat;
    }
    ll up(ll idx){
        if(idx==-1){
            return -1;
        }
        auto loc = locs(idx);
        if(get<0>(loc)>0){
            return idx-w;
        }
        return -1;
    }
    ll down(ll idx){
        if(idx==-1){
            return -1;
        }
        auto loc = locs(idx);
        if(get<0>(loc)<h-1){
            return idx+w;
        }
        return -1;
    }
    ll left(ll idx){
        if(idx==-1){
            return -1;
        }
        auto loc = locs(idx);
        if(get<1>(loc)>0){
            return idx-1;
        }
        return -1;
    }
    ll right(ll idx){
        if(idx==-1){
            return -1;
        }
        auto loc = locs(idx);
        if(get<1>(loc)<w-1){
            return idx+1;
        }
        return -1;
    }
    tuple<ll,ll,ll> locs(ll idx){
        return make_tuple(idx%(h*w)/w,idx%w,idx/h*w);
    }
    bool valid(ll r,ll c, ll pat){
        if(0<=r&&r<h&&0<=c&&c<w&&0<pat&&pat<p){
            return true;
        }
        return false;
    }
};
//using bint = boost::multiprecision::cpp_int;
int main(){
    ll n;
    string s;
    cin >> n >> s;
    ll ab = 0;
    ll cd = 0;
    for(ll i = 0; i < n; ++i){
        if(s[i]=='A'||s[i]=='B'){
            ab++;
        }else{
            cd++;
        }
    }
    vector<cell::modint998244353> v(300001,1);
    for(ll i = 1; i < 300001; ++i){
        v[i]=v[i-1]*cell::modint998244353(i);
    }
    auto ans = v[ab+cd]/v[ab]/v[cd];
    cout << ans.value << endl;
}