//まずはTLEしそうな解法から #include #include #define rep(i, n) for (i = 0; i < n; i++) using namespace std; const int mod = 998244353; int n; string s; int dp[50001][27][27]; //dp[len][2文字前][直前], ブランク: 26番 signed main() { int i, j, k, l; cin >> n >> s; dp[0][26][26] = 1; rep(i, n) { rep(j, 27) { rep(k, 27) { if (dp[i][j][k] == 0) continue; if (s[i] != '?') { l = s[i] - 'a'; if (j == l || k == l) continue; dp[i + 1][k][l] += dp[i][j][k]; if (dp[i + 1][k][l] >= mod) dp[i + 1][k][l] -= mod; } else { rep(l, 26) { //ブランク = 26は含まないので注意 if (j == l || k == l) continue; dp[i + 1][k][l] += dp[i][j][k]; if (dp[i + 1][k][l] >= mod) dp[i + 1][k][l] -= mod; } } } } } int ans = 0; rep(j, 27) { rep(k, 27) { ans += dp[n][j][k]; if (ans >= mod) ans -= mod; } } cout << ans << endl; return 0; }