/* #define _GLIBCXX_DEBUG //*/ #include /* #include using namespace atcoder; //*/ using namespace std; #define dbl double #define ll long long #define ull unsigned long long #define ld long double #define pii pair #define pll pair #define ti3 tuple #define tl3 tuple #define vi vector #define vc vector #define vl vector #define vb vector #define vs vector #define vvi vector> #define vvc vector> #define vvb vector> #define vvl vector> #define vvvi vector>> #define vvvc vector>> #define vvvl vector>> #define vvvvi vector>>> #define vvvvc vector>>> #define vvvvl vector>>> #define vpi vector #define vpl vector #define prq priority_queue #define prq2 priority_queue> #define seti set #define setl set #define quel queue #define pb push_back #define ps push #define ins insert #define rev reverse #define fi first #define se second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(),x.end() #define forv(i,V) for(const auto& i:V) #define rep(i,n) for (ll i = 0; i < (ll)(n); i++) #define repi(i,j,n) for (ll i = (ll)(j);i < (ll)(n);i++) #define rep2(i,n) for(ll i=(ll)(n-1);i>=0ll;i--) #define repi2(i,n,j) for(ll i=(ll)(n-1);i>=(ll)(j);i--) #define faster ios::sync_with_stdio(false);std::cin.tie(nullptr); const double PI=3.14159265358979323846; vl dxs = {1, 0, -1, 0}; vl dys = {0, 1, 0, -1}; ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max((ll)b,a);} ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min((ll)b,a);} ll gcd(ll a,ll b){if(b==0){return a;}else{return gcd(b,a%b);}} ll lcm(ll a,ll b){return (a/gcd(a,b))*b;} ll indexlb(vl &v,ll x){auto it=lb(all(v),x);ll index=it-v.begin();return index;} ll indexub(vl &v,ll x){auto it=ub(all(v),x);ll index=it-v.begin();return index;} ll setlb(setl &s,ll x){auto it=s.lb(x); return *it;}//番目ではなく要素が返ってくる ll setub(setl &s,ll x){auto it=s.ub(x); return *it;}//番目ではなく要素が返ってくる void setpre(double d,ll x){cout< void output(vector &A) {rep(i,A.size()){cout< void cinvec(vector &A){rep(i,A.size()) cin>>A[i];} template void coutvece(vector &A){for(ll i=0;i bool chmin(T &a,const T &b){if(b bool chmax(T &a,const T &b){if(b>a){a=b; return 1;} return 0;} void yesno(bool i){if(i)cout<<"yes"<0) { if(n&1) res=(res*a)%mod; a=a*a%mod; n>>=1; } return res; } vl factt,invv,fact_inv; void combjyunbi(ll size,ll mod){ factt.resize(size+5); fact_inv.resize(size+5); invv.resize(size+5); factt[0]=factt[1]=1; fact_inv[0]=fact_inv[1]=1; invv[1]=1; repi(i,2,size+5){ factt[i]=factt[i-1]*i%mod; invv[i]=mod-invv[mod%i]*(mod/i)%mod; fact_inv[i]=fact_inv[i-1]*invv[i]%mod; } } //combjyunbiしてから!!! ll combmod(ll n,ll k,ll mod){ return factt[n]*(fact_inv[k]*fact_inv[n-k]%mod)%mod; } ll combmod2(ll n,ll k,ll mod){ ll ans=1; repi(i,1,k+1){ ans*=modwari(n-i+1,i,mod); ans%=mod; } return ans; } //nが大きく、kが小さい場合(計算量はO(k)) struct edge { ll from; //辺の始点 ll to; //辺の終点 ll leng; //辺の重み }; struct yukoedge{ ll to; }; using Graph =vvl; using Graph2=vector>; using Graph3=vector>;//.pb({x})で作成 vl topo_sort(const Graph3 &G){//bfs できない場合は返り値のsize≠n vl ans; ll n=G.size(); vl ind(n);// ind[i]: 頂点iに入る辺の数(次数) rep(i,n){//count index forv(e,G[i]){ ind[e.to]++; } } quel que;//辞書順最小が欲しかったらprq2にする rep(i,n){//次数が0の点 if(ind[i]==0){ que.push(i); } } while(!que.empty()){//bfs ll now=que.front(); ans.pb(now); que.pop(); forv(e,G[now]){ ind[e.to]--; if(ind[e.to]==0) { que.push(e.to); } } } return ans; } vl sieve(ll n){ //fast_soinsuの前処理 O(NloglogN) //vl min_factor=sieve(1e6)などでコピー vl min_factor(n+1); rep(i,n+1) min_factor[i] = i; for(ll i=2;i*i<=n;i++){ if(min_factor[i]==i){ for(ll j=2;i*j<= n;j++){ if(min_factor[i*j]>i){ min_factor[i*j]=i; } } } } return min_factor; } vl fast_soinsu(const vl &min_factor,ll m){ //N以下の正整数すべてを素因数分解するときに有効 //vl min_factor=sieve(1e6);で前計算 O(NloglogN) //vl g=soinsu(min_factor,i);でコピー //本計算の計算量は O(logN) vl ans; while(m>1){ ans.pb(min_factor[m]); m/=min_factor[m]; } return ans; } vector factorize(ll n){//素因数分解 {因数,乗数} vector ans; for(ll a=2;a*a<=n;a++){ if(n%a!=0) continue; ll ex=0; while(n%a==0){ ex++; n/=a; } ans.pb({a,ex}); } if(n!=1) ans.push_back({n, 1}); return ans; } vl divisor(ll n){//約数列挙(sqrt(n)) vl ret; for(ll i=1;i*i<=n;i++){ if(n%i==0){ ret.push_back(i); if(i*i!=n) ret.push_back(n/i); } } sort(all(ret)); return ret; } vector> rle(string s){//ランレングス圧縮(数,文字) ll n=s.length(); vector> res; char pre=s[0]; ll cnt=1; repi(i,1,n) { if(pre!=s[i]){ res.push_back({cnt,pre}); pre=s[i]; cnt=1; } else cnt++; } res.push_back({cnt,pre}); return res; } vl bfs(Graph G,ll s){//始点sからの距離 ll n=G.size(); vl dist(n,-1); quel que; dist[s]=0; que.push(s); while (!que.empty()) { ll v=que.front(); que.pop(); forv(nv,G[v]) { if (dist[nv]!=-1) continue; dist[nv]=dist[v]+1; que.push(nv); } } return dist; } template vector jyu_nasi(vector a){//sortしてから!配列を重複なしにする a.erase(unique(all(a)),a.end()); return a; } map zaatu(vl &a,ll t){//O(NlogN) キーが返され、配列は圧縮済みのものになる map poi; vl copy=a; sort(all(copy)); copy=jyu_nasi(copy); vl res(a.size()); rep(i,a.size()){ if(t==0) poi[indexlb(copy,a[i])]=a[i];//t=0ならキーは圧縮、1ならキーは元の要素 else poi[a[i]]=indexlb(copy,a[i]); res[i]=indexlb(copy,a[i]); } a=res; return poi; } vl ruisekiwa(vl a){//累積和とる ll n=a.size(); vl res(n); res[0]=a[0]; repi(i,1,n){ res[i]=res[i-1]+a[i]; } return res; } struct unionfind{ vl p; unionfind(ll n):p(n,-1){}//rootなら-1*連結成分のサイズ ll root(ll x){ if(p[x]<0){ return x; } else{ p[x]=root(p[x]); return p[x]; } } ll size(ll x){ return -p[root(x)]; } bool same(ll x,ll y){ return root(x)==root(y); } void merge(ll x,ll y){ x=root(x); y=root(y); if(x==y) return; if(size(x)>s; ll n=s.size(); vvvl dp(n,vvl(3,vl(26,0))); dp[0][0][s[0]-'A']++; repi(i,1,n){ dp[i][0][s[i]-'A']++; rep(j,3){ rep(f,26){ if(dp[i-1][j][f]!=0){ dp[i][j][f]+=dp[i-1][j][f]; if(j==0){ if(f==s[i]-'A'){ dp[i][j+1][f]+=dp[i-1][j][f]; } } else if(j==1){ if(f!=s[i]-'A'){ dp[i][j+1][s[i]-'A']+=dp[i-1][j][f]; } } } } } } ll ans=0; rep(i,26){ ans+=dp[n-1][2][i]; } cout<