Bovine Genetics

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 9;
const int M = 5;
const int MOD = 1e9 + 7;

int dp[N][M][M][M];

int main () {
    string s, deCode = "AGCT";
    cin >> s;
    int n = s.length();
    for (int n = 0; n < 4; n++)
        for (int l = 0; l < 4; l++)
            if (s[0] == '?' || s[0] == deCode[l])
                dp[0][n][l][l] = 1;
    for (int k = 1; k < s.length(); k++) {
        for (int m2 = 0; m2 < 4; m2++) {
            if (s[k] == '?' || s[k] == deCode[m2]) {
                for (int n = 0; n < 4; n++) {
                    for (int l = 0; l < 4; l++) {
                        for (int m = 0; m < 4; m++) {
                            if (m != m2) {
                                dp[k][n][l][m2] += dp[k - 1][n][l][m];
                                dp[k][n][l][m2] %= MOD;
                            }

                            if (n == m) {
                                dp[k][l][m2][m2] += dp[k - 1][n][l][m];
                                dp[k][l][m2][m2] %= MOD;
                            }
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for (int l = 0; l < 4; l++) {
        for (int m = 0; m < 4; m++) {
            res += dp[s.length() - 1][m][l][m];
            res %= MOD;
        }
    }
    cout << res << "\n";
    return 0;
}