#include #include #define fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr) #define eb emplace_back #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; using mint = atcoder::modint998244353; constexpr ll inf = 2e18; constexpr int mod = 998244353; #ifdef LOCAL #define debug(x) std::cerr << #x << " = " << (x) << std::endl; #else #define debug(x) #endif static void judge(bool c) { std::cout << (c ? "Yes" : "No") << '\n'; } // https://nononmath.hatenablog.com/entry/2024/06/11/193707 template mint bounded_increasing_sequence(const vector &A) { const int n = A.size(); const int m = A[n - 1]; // 階乗とその逆元の前計算 vector fac(n + m + 1), finv(n + m + 1); { fac[0] = 1; for (int i = 1; i <= n + m; i++) fac[i] = i * fac[i - 1]; finv[n + m] = fac[n + m].inv(); for (int i = n + m; i >= 1; i--) finv[i - 1] = i * finv[i]; } auto rec = [&](const auto &rec, int l, int r, int d, const vector &bottom_edge) -> vector { if (l + 1 == r) { return vector(A[l] - d, l == 0 ? mint::raw(1) : bottom_edge[0]); } int m = (l + r) / 2; int h = A[m] - d, w = r - m; // 左下の計算 auto left_edge = rec(rec, l, m, d, vector(bottom_edge.begin(), bottom_edge.begin() + m - l)); left_edge.resize(h); vector top_edge(w); // 左から上への寄与 if (h) { vector f(h), g(h + w); for (int i = 0; i < h; i++) f[i] = left_edge[i] * finv[h - 1 - i]; for (int i = 0; i < h + w; i++) g[i] = fac[i]; f = convolution(f, g); for (int i = 0; i < w; i++) top_edge[i] += finv[i] * f[h - 1 + i]; } // 下から上への寄与 if (h) { vector f(w), g(w); for (int i = 0; i < w; i++) f[i] = bottom_edge[i + m - l]; for (int i = 0; i < w; i++) g[i] = fac[h - 1 + i] * finv[i]; f = convolution(f, g); for (int i = 0; i < w; i++) top_edge[i] += finv[h - 1] * f[i]; } else { for (int i = 0; i < w; i++) top_edge[i] = bottom_edge[i + m - l]; } vector right_edge(A[r - 1] - d); // 左から右への寄与 if (h) { vector f(h), g(h + w); for (int i = 0; i < h; i++) f[i] = left_edge[i]; for (int i = 0; i < h + w; i++) g[i] = fac[w - 1 + i] * finv[i]; f = convolution(f, g); for (int i = 0; i < h; i++) right_edge[i] += finv[w - 1] * f[i]; } // 下から右への寄与 if (h) { vector f(w), g(h + w); for (int i = 0; i < w; i++) f[i] = bottom_edge[m - l + i] * finv[w - 1 - i]; for (int i = 0; i < h + w; i++) g[i] = fac[i]; f = convolution(f, g); for (int i = 0; i < h; i++) right_edge[i] += finv[i] * f[w - 1 + i]; } vector upper_right = rec(rec, m, r, A[m], top_edge); int k = upper_right.size(); // 右側の情報のマージ for (int i = 0; i < k; i++) right_edge[i + h] += upper_right[i]; return right_edge; }; vector right_edge = rec(rec, 0, n, 0, vector(n)); mint res = 0; for (mint x : right_edge) res += x; return res; } string s; int main(){ cin >> s; int n = s.size(),k = 0; vector a; for(int i = 0; i < n; i++){ if(s[i] == 'A') a.eb(i + 1), k++; } for(int i = 0; i < k; i++){ a[i] -= i; } // 0\le B_i < A_i, B_i \le B_{i+1} を数える cout << bounded_increasing_sequence(a).val() << endl; }