考虑相邻两字符连边，问题转化为通路个数。

考虑 BEST 定理。

BEST 定理：有向图欧拉回路数 $P=T\prod(outdeg_i-1)!$，其中 $T$ 是原图外向生成树个数。

下文使用图来表示有向图。

显然，$T$ 可以使用矩阵树定理求出，而我们想知道的是如何将欧拉通路转化为欧拉回路。

考虑一个图可以有一条欧拉回路当且仅当所有顶点的入度与出度相等。而有欧拉通路则有两个点的入度出度不等。显然我们就可以确定起点 $s$，终点 $t$。我们加一条 $t\rightarrow s$ 的边然后跑 BEST 即可。

如果起点终点未确定，那么每一个循环重构都可以给答案贡献一次，总次数为 $n-1$，总数要乘 $n-1$。

每条边是相同的，所以我们需要除去 $c(u,v)!$，其中 $c(u,v)$ 表示 $u$ 到 $v$ 的边数。

然后就是 BEST 定理板子了。

#include<iostream>
#include<algorithm>
#include<vector>
using ll=long long;
const int sz=1e6+10;
const ll mod=1e9+7;
ll fact[sz],inv[sz];
ll qpow(ll base,ll exp){
  ll ans=1;
  while(exp!=0){
    if(exp&1)ans=ans*base%mod;
    base=base*base%mod,exp>>=1;
  }
  return ans;
}
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin>>t>>t;
  while(t--)[](){
    int n,N=3;
    std::string str;
    std::cin>>str,n=str.size(),str=" "+str;
    if(n==1)return std::cout<<"3\n",void();
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i%mod;
    inv[n]=qpow(fact[n],mod-2);
    for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    std::vector<std::vector<int>>cnt(3,std::vector<int>(3));
    std::vector<std::vector<ll>>det(3,std::vector<ll>(3));
    std::vector<int>ind(3),oud(3);
    for(int i=1;i<n;i++){
      int u=str[i]-'a',v=str[i+1]-'a';
      oud[u]++,ind[v]++;
      det[v][v]++,det[u][v]--,cnt[u][v]++;
    }
    int s=-1,t=-1;
    for(int i=0;i<N;i++){
      if(ind[i]<oud[i])s=i,ind[s]++;
      if(ind[i]>oud[i])t=i,oud[t]++;
    }
    ll ans=1;
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)ans=ans*inv[cnt[i][j]]%mod;
    for(int i=0;i<N;i++)ans=ans*fact[std::max(oud[i]-1,0)]%mod;
    std::vector<bool>sim(3);
    for(int i=0;i<N;i++)sim[i]=oud[i]==0;
    for(int i=0;i<N;i++){
      if(!sim[i]){
        sim[i]=true;
        break;
      }
    }
    ll res=1;
    if(s!=-1)det[s][s]++,det[t][s]--;
    if(!sim[0]&&!sim[1])res=det[0][0]*det[1][1]-det[1][0]*det[0][1];
    if(!sim[0]&&!sim[2])res=det[0][0]*det[2][2]-det[2][0]*det[0][2];
    if(!sim[1]&&!sim[2])res=det[1][1]*det[2][2]-det[1][2]*det[2][1];
    if(sim[0]+sim[1]+sim[2]==2)res=det[0][0]*(1-sim[0])+det[1][1]*(1-sim[1])+det[2][2]*(1-sim[2]);
    ans=ans*(res%mod+mod)%mod;
    if(s==-1)ans=ans*(n-1)%mod;
    std::cout<<ans<<"\n";
  }();
  return 0;
}