#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #define se second #define fi first using namespace std; using ll = long long; using ull = unsigned long long; #define rep(i,n) for(long long i = 0; i < (int)n; i++) #define FOR(i, m, n) for(long long i = (m);i < (n); ++i) #define RFOR(i, n, m) for(long long i = (m-1);i >= (n); --i) #define ALL(obj) (obj).begin(),(obj).end() #define SPEED cin.tie(0);ios::sync_with_stdio(false); template using V = vector; template using P = pair; template using PQ = priority_queue; template using PQR = priority_queue,greater>; void print(V ar) { for(auto x: ar)cout << x << " " ; cout << endl; } #include #include #include #include template struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} lazy_segtree(const std::vector& v) : _n(int(v.size())) { /* log = internal::ceil_pow2(_n); size = 1 << log; */ log = 0; size = 1; while (size < _n) size <<= 1, log++; d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; using namespace std; int op(int a, int b){return max(a,b);} int e(){return 0;} int mapping(int f, int x){ if (f == -1) return x; return f; } int composition(int f, int g){ if (f == -1) return g; return f; } int id(){return -1;} V> G, RG; V df1,df2,dg1,dg2; ll f1(int x) { if(df1[x]!=-1) { return df1[x]; } ll r = 0; for(int y:RG[x]) { r+=f1(y); } df1[x] = r; return df1[x]; } ll f2(int x) { if(df2[x]!=-1) { return df2[x]; } ll r = 0; for(int y:G[x]) { r+=f2(y); } df2[x] = r; return df2[x]; } ll g1(int x) { if(dg1[x]!=-1) { return dg1[x]; } ll r = 0; for(int y:RG[x]) { r+=f1(y)+g1(y); } dg1[x] = r; return dg1[x]; } ll g2(int x) { if(dg2[x]!=-1) { return dg2[x]; } ll r = 0; for(int y:G[x]) { r+=f2(y)+g2(y); } dg2[x] = r; return dg2[x]; } int main(){ int n;cin >> n; string s;cin >> s; const int m = 26; V S(n);rep(i, n)S[i] = s[i]-'a'; const ll mod = 998244353; V>> dp(n+1,V>(2, V(2, 0))); dp[0][0][0] = 1; rep(i, n)rep(j, 2)rep(k, 2)rep(l, m) { int now = dp[i][j][k]; int ni = i+1, nj = j, nk = k; if(j==0 && l > S[i])continue; if(j==0 && l < S[i])nj = 1; if(l == 0)nk += 1; if(nk==2)continue; dp[ni][nj][nk] += now; if(dp[ni][nj][nk] >= mod)dp[ni][nj][nk]-=mod; } cout << (dp[n][1][1])%mod << endl; }