RT，按照第一篇题解写的暴力，结果样例 2 都过不去。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int mod=(int)(1e9+7),N=(int)(1e5+5);
char s[N];
int n,a[N],f[1000][4];

bool chk(int l,int r) {
	for(int i=l;i<r;i++) if(a[i]==a[i+1]) return 0;
	return 1;
}

bool chkv(int x,int y) {
	if(x==4) return 1;
	return x==y;
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>s+1; n=strlen(s+1);
	for(int i=1;i<=n;i++) {
		if(s[i]=='A') a[i]=0;
		else if(s[i]=='C') a[i]=1;
		else if(s[i]=='G') a[i]=2;
		else if(s[i]=='T') a[i]=3;
		else a[i]=4;
	}
//	f[0][0]=f[0][1]=f[0][2]=f[0][3]=1;
	if(a[1]==4) {
		f[1][0]=f[1][1]=f[1][2]=f[1][3]=1;
	} else {
		f[1][a[1]]=1;
	}
	for(int i=2;i<=n;i++) {
		for(int x=0;x<4;x++) {
			for(int j=i-1;j>=0;j--) {
				for(int y=0;y<4;y++) {
					if(chkv(a[j+1],x)&&chkv(a[i],y)&&chk(j+1,i)) {
						if(j) f[i][x]=(f[i][x]+f[j][y])%mod;
						else f[i][x]=(f[i][x]+1)%mod;
//						cout<<i<<" "<<x<<" "<<f[i][x]<<'\n';
					}
				}
			}
		}	
	}
	int ans=0;
	for(int i=0;i<4;i++) ans=(ans+f[n][i])%mod;
	cout<<ans;
	return 0;
}