爆标做法。考虑把 DP 套 DP 直接扔掉，钦定当前状态按后 $1/2/4$ 个分段，强行分讨去掉重复情况：

最后一个分段，$f_i\gets f_i+f_{i-1}$；

若 $[i-1,i]$ 相邻，最后两个分段，要求这两个交换，否则被两个 $1$ 段替代，$f_i\gets f_i+f_{i-2}$。

若 $[i-3,i]$ 是正方形，最后四个分段，先让 $f_i\gets f_i+24f_{i-4}$，然后扣掉可以被替代的方案。

被 $i$ 分一段的某个方案替代：

若 $[i-3,i]$ 顺序是 $1234$，被四个 $1$ 段替代，$f_i\gets f_i-f_{i-4}$。

若 $[i-3,i]$ 顺序是 $2314,3124,3214$，这三种情况只可能被 $[i-4,i-1]$ 分段的情况替代，若 $[i-4,i-1]$ 是正方形则 $f_i\gets f_i-3f_{i-5}$。

若 $[i-3,i]$ 顺序是 $1324$，若 $[i-2,i-1]$ 相邻，此时可以钦定为按 $i-3,[i-2,i-1]$ 分段。若 $[i-4,i-1]$ 分段，能被 $[i-4,i-3],[i-2,i-1]$ 替代。若按 $[i-5,i-4]$ 分段，能被 $i-5,i-4$ 替代；若按 $[i-7,i-4]$ 分段，在 $[i-7,i-5]$ 中必有两个相邻，可以 $2+1$ 分段。因此可以转移 $f_i\gets f_i-f_{i-4}$，否则若 $[i-5,i-1]$ 是正方形就转移 $f_i\gets f_i-f_{i-5}$。

若 $[i-3,i]$ 顺序是 $2134$，若 $i-3,i-2$ 相邻，钦定 $[i-3,i-2],i-1,i$ 分段，$[i-5,i-2]$ 分段的情况一定有 $[i-5,i-4]$ 相邻，总是可以分成两段 $2$，因此已经被包含，转移 $f_i\gets f_i-f_{i-4}$。否则情况比较复杂：

如果能分段 $[i-4,i-1]$，就是 $f_{i-4}$。另一种方案是分段 $i-1,i$ 且 $[i-5,i-2]$ 的顺序是 $2143$（$i-5,i-4$ 必须交换，否则被 $[i-4,i-1]$ 分段的情况覆盖）。我们已知 $[i-3,i-2]$ 在交错的位置，因此 $[i-5,i-2]$ 必须能成段。注意，此时我们的前提条件是扣除 $[i-3,i]$ 成段的方案数。

现在我们考虑 $[i-3,i]$ 成段时 $[i-7,i-4]$ 要成段，考虑 $i-7,i-6$ 是否交换。若不交换，那这两个成段的限制已经满足，为 $f_{i-8}$。否则限制变为 $[i-5,i-2],[i-7,i-4]$ 要能成段且 $i-7,i-6$ 必须交换。发现这变成了一个子问题，我们可以拿一个 $g_i$ 算出，为 $g_i=\begin{cases}g_{i-2}+f_{i-4}&\ [i-3,i]\text{ is valid}\\0&\ \text{otherwise}\end{cases}$。转移就是 $f_i\gets f_i-g_{i-4}$。

若 $[i-4,i-1]$ 不能分段，就只有分段 $i-1,i,[i-5,i-2]$，比上面多一种 $i-5,i-4$ 不交换的情况 $f_{i-6}$。转移是 $f_i\gets f_i-f_{i-6}-g_{i-4}$。

若被 $[i-1,i]$ 分一段的某个方案替代（首先要求 $i-1,i$ 相邻）：

$i$ 不能留在原位，否则被上一种情况统计，因此只有 $2143,1243$ 型。

对 $1243$ 型，可以钦定为按 $[i-4,i-3],[i-2,i-1]$ 分段。这要求 $i-4$ 是断点，和上面的讨论类似，若按 $[i-6,i-3]$ 分段能拆成 $2+2$，若按 $[i-7,i-4]$ 分段能将 $[i-7,i-5]$ 拆成 $i+2$。转移 $f_i\gets f_i-f_{i-4}$。

对 $2143$ 型，因为 $[i-3,i-2]$ 也相邻，就能被 $[i-3,i-2],[i-1,i]$ 替代（同上，$[i-5,i-2]$ 分段的情况被包含）。转移 $f_i\gets f_i-f_{i-4}$。

综上，我们做到了小常数 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int t,n,f[100005],g[100005];
char s[100005];
bool check2(int x){
  return x>=2&&(abs(s[x]-s[x-1])==3||(abs(s[x]-s[x-1])==1&&(s[x]+s[x-1])%3!=1));
}
bool check4(int x){
  if(x<4)return 0;
  int t=0;
  for(int i=0;i<4;i++)t|=1<<(s[x-i]-'0');
  return t==54||t==108||t==432||t==864;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),f[0]=1,cin>>t;
  while(t--){
    cin>>s+1,n=strlen(s+1);
    for(int i=1;i<=n;i++){
      g[i]=check4(i)?(g[i-2]+f[i-4])%mod:0,f[i]=f[i-1];
      if(check2(i))f[i]=(f[i]+f[i-2])%mod;
      if(check4(i)){
        f[i]=(f[i]+23ll*f[i-4])%mod;
        if(check4(i-1))f[i]=((f[i]-3ll*f[i-5])%mod+mod)%mod;
        if(check2(i-1))f[i]=(f[i]-f[i-4]+mod)%mod;
        else if(check4(i-1))f[i]=(f[i]-f[i-5]+mod)%mod;
        if(check2(i-2))f[i]=(f[i]-f[i-4]+mod)%mod;
        else{
          if(check4(i-1)){
            f[i]=(f[i]-f[i-5]+mod)%mod;
            if(check4(i-2))f[i]=(f[i]-g[i-4]+mod)%mod;
          }
          else f[i]=(f[i]-g[i-2]+mod)%mod;
        }
        if(check2(i))f[i]=(f[i]-2ll*f[i-4]%mod+2*mod)%mod;
      }
    }
    cout<<f[n]<<'\n';
  }
  return 0;
}

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=1e5+9,Mod=1e9+7;
int T,n,a[N];
char s[N];
bool chk2(array<int,2>a){
    sort(a.begin(),a.end());
    if(a[0]+3==a[1])return 1;
    if(a[0]+1==a[1]&&a[0]!=3&&a[0]!=6)return 1;
    return 0;
}
bool chk4(array<int,4>a){
    sort(a.begin(),a.end());
    if(a[0]==1&&a[1]==2&&a[2]==4&&a[3]==5)return 1;
    if(a[0]==2&&a[1]==3&&a[2]==5&&a[3]==6)return 1;
    if(a[0]==4&&a[1]==5&&a[2]==7&&a[3]==8)return 1;
    if(a[0]==5&&a[1]==6&&a[2]==8&&a[3]==9)return 1;
    return 0;
}
bool equ(vector<int>a,vector<int>b){sort(a.begin(),a.end()),sort(b.begin(),b.end());return a==b;}
void Upd(int&x,int y){
    x+=y;
    if(x>=Mod)x-=Mod;
}
int f[2][16005],cur;
vector<int>S;
bool vis[16005],ck2[N],ck4[N];
bool good1[10][10][10],good2[10][10];
int H(int x,int y,int z,int a,int b,int c,int d){return x*1600+y*160+z*16+a*8+b*4+c*2+d;}
void solve(){
    cin>>s+1,n=strlen(s+1);
    rep(i,1,n)a[i]=s[i]-'0';
    memset(f,0,sizeof(f)),memset(vis,0,sizeof(vis)),cur=0;
    f[0][1]=1,S.push_back(1);
    rep(i,0,n+1)ck2[i]=ck4[i]=0;
    rep(i,2,n)ck2[i]=chk2({a[i-1],a[i]});
    rep(i,4,n)ck4[i]=chk4({a[i-3],a[i-2],a[i-1],a[i]});
    rep(i,1,n){
        memset(f[cur^1],0,sizeof(f[cur^1]));
        vector<int>nS;
        for(int s:S)vis[s]=0;
        vector<int>trs;
        rep(j,max(1,i-3),min(n,i+3))trs.push_back(a[j]);
        sort(trs.begin(),trs.end());
        trs.resize(unique(trs.begin(),trs.end())-trs.begin());
        for(int s:S){
            int a3=(s>>4)/100,a2=(s>>4)/10%10,a1=(s>>4)%10,f3=(s>>3)&1,f2=(s>>2)&1,f1=(s>>1)&1,f0=s&1;
            int val=f[cur][s];
            for(int a0:trs){
                int nf=0;
                if(a[i]==a0)nf|=f0;
                if(!nf){
                    if(i>1&&ck2[i]&&equ({a[i-1],a[i]},{a1,a0}))nf|=f1;
                    if(!nf&&i>3&&ck4[i]&&equ({a[i-3],a[i-2],a[i-1],a[i]},{a3,a2,a1,a0}))nf|=f3;
                }
                if(f2+f1+f0+nf==0)continue;
                int na2=a2,na1=a1,na0=a0,nf2=f2,nf1=f1;
                if(!f2)na2=0;
                if(!f2&&!f1)na1=0;
                if(!f2&&!f1&&!f0)na0=0;
                if(!good1[na2][na1][na0])na2=0,nf2=0;
                if(!good2[na1][na0])na1=0,nf1=0;
                int nH=H(na2,na1,na0,nf2,nf1,f0,nf);
                if(!vis[nH])vis[nH]=1,nS.push_back(nH);
                Upd(f[cur^1][nH],val);
            }
            f[cur][s]=0;
        }
        S=nS,cur^=1;
    }
    int ans=0;
    for(int s:S)if(s&1)Upd(ans,f[cur][s]);
    cout<<ans<<'\n';
}
int main(){
    cin>>T;
    rep(i,0,9)rep(j,0,9)rep(k,0,9)rep(l,0,9)if(chk4({i,j,k,l}))good1[i][j][k]=good2[i][j]=1;
    while(T--)solve();
    return 0;
}