题解

#include<iostream>
#include<cstring>
#define ll long long
#define mo 1000000007

using namespace std;

char c[100001];
ll f[100001][4][4][4], ans;
int n;

int get_bh(char x) {
	if (x == 'A') return 0;
	if (x == 'C') return 1;
	if (x == 'G') return 2;
	return 3;
}

int main() {
	cin>>c+1;
	n = strlen(c + 1);
	
	if (c[1] == '?') {
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				f[1][i][i][j] = 1;
	}
	else {
		for (int j = 0; j < 4; j++)
			f[1][get_bh(c[1])][get_bh(c[1])][j] = 1;
	}
	
	for (int i = 2; i <= n; i++)
		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
				for (int l = 0; l < 4; l++) {
					int now = get_bh(c[i]);
					if (c[i] == '?') {
						for (now = 0; now < 4; now++) {
							if (now != k) {
								f[i][j][now][l] = (f[i][j][now][l] + f[i - 1][j][k][l]) % mo;
							}
							if (k == l) {
								f[i][now][now][j] = (f[i][now][now][j] + f[i - 1][j][k][l]) % mo;
							}
						}
					}
					else {
						if (now != k) {
							f[i][j][now][l] = (f[i][j][now][l] + f[i - 1][j][k][l]) % mo;
						}
						if (k == l) {
							f[i][now][now][j] = (f[i][now][now][j] + f[i - 1][j][k][l]) % mo;
						}
					}
				}
	
	for (int j = 0; j < 4; j++)
		for (int k = 0; k < 4; k++)
			ans = (ans + f[n][j][k][k]) % mo;
	cout<<ans;
	
	return 0;
}