#line 1 "main.cpp" #include #line 2 "/home/ubuntu/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 4 "/home/ubuntu/Library/modulus/modpow.hpp" inline int32_t modpow(uint_fast64_t x, uint64_t k, int32_t MOD) { assert (/* 0 <= x and */ x < (uint_fast64_t)MOD); uint_fast64_t y = 1; for (; k; k >>= 1) { if (k & 1) (y *= x) %= MOD; (x *= x) %= MOD; } assert (/* 0 <= y and */ y < (uint_fast64_t)MOD); return y; } #line 5 "/home/ubuntu/Library/modulus/modinv.hpp" inline int32_t modinv_nocheck(int32_t value, int32_t MOD) { assert (0 <= value and value < MOD); if (value == 0) return -1; int64_t a = value, b = MOD; int64_t x = 0, y = 1; for (int64_t u = 1, v = 0; a; ) { int64_t q = b / a; x -= q * u; std::swap(x, u); y -= q * v; std::swap(y, v); b -= q * a; std::swap(b, a); } if (not (value * x + MOD * y == b and b == 1)) return -1; if (x < 0) x += MOD; assert (0 <= x and x < MOD); return x; } inline int32_t modinv(int32_t x, int32_t MOD) { int32_t y = modinv_nocheck(x, MOD); assert (y != -1); return y; } #line 6 "/home/ubuntu/Library/modulus/mint.hpp" /** * @brief quotient ring / 剰余環 $\mathbb{Z}/n\mathbb{Z}$ */ template struct mint { int32_t value; mint() : value() {} mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {} mint(int32_t value_, std::nullptr_t) : value(value_) {} explicit operator bool() const { return value; } inline mint operator + (mint other) const { return mint(*this) += other; } inline mint operator - (mint other) const { return mint(*this) -= other; } inline mint operator * (mint other) const { return mint(*this) *= other; } inline mint & operator += (mint other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; } inline mint & operator -= (mint other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; } inline mint & operator *= (mint other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; } inline mint operator - () const { return mint(this->value ? MOD - this->value : 0, nullptr); } inline bool operator == (mint other) const { return value == other.value; } inline bool operator != (mint other) const { return value != other.value; } inline mint pow(uint64_t k) const { return mint(modpow(value, k, MOD), nullptr); } inline mint inv() const { return mint(modinv(value, MOD), nullptr); } inline mint operator / (mint other) const { return *this * other.inv(); } inline mint & operator /= (mint other) { return *this *= other.inv(); } }; template mint operator + (int64_t value, mint n) { return mint(value) + n; } template mint operator - (int64_t value, mint n) { return mint(value) - n; } template mint operator * (int64_t value, mint n) { return mint(value) * n; } template mint operator / (int64_t value, mint n) { return mint(value) / n; } template std::istream & operator >> (std::istream & in, mint & n) { int64_t value; in >> value; n = value; return in; } template std::ostream & operator << (std::ostream & out, mint n) { return out << n.value; } #line 4 "main.cpp" using namespace std; constexpr int64_t MOD = 998244353; mint solve(int64_t n, std::string s) { array, 27>, 27> cur = {}; cur[26][26] += 1; for (char c : s) { array, 27>, 27> prv = {}; cur.swap(prv); REP (k, 26) { if (k == c - 'a' or c == '?') { REP (i, 27) { REP (j, 27) { if (i != k and j != k) { cur[j][k] += prv[i][j]; } } } } } } mint ans = 0; REP (i, 27) { REP (j, 27) { ans += cur[i][j]; } } return ans; } // generated by oj-template v4.8.0 (https://github.com/online-judge-tools/template-generator) int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int64_t N; std::string S; std::cin >> N >> S; auto ans = solve(N, S); std::cout << ans << '\n'; return 0; }