結果
| 問題 |
No.3370 AB → BA
|
| コンテスト | |
| ユーザー |
 りすりす/TwoSquirrels
|
| 提出日時 | 2025-11-18 15:39:53 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,086 bytes |
| コンパイル時間 | 11,899 ms |
| コンパイル使用メモリ | 659,432 KB |
| 実行使用メモリ | 38,276 KB |
| 最終ジャッジ日時 | 2025-11-18 15:40:21 |
| 合計ジャッジ時間 | 25,427 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 3 WA * 13 RE * 4 |
ソースコード
// SPDX-License-Identifier: MIT
// (c) 2023 TwoSquirrels
// my AtCoder environment: https://github.com/TwoSquirrels/atcoder-env
//#define DEBUG
// enable debug mode when compiled with -DDEBUG
#ifdef DEBUG
# define IS_DEBUG (1)
#else
// QCFium method
//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
# define IS_DEBUG (0)
#endif
/// includes
// standard libraries
#if __has_include(<bits/stdc++.h>)
# include <bits/stdc++.h>
#else // <bits/stdc++.h>
// C++17 (clang)
# include <cassert>
# include <cfenv>
# include <cfloat>
# include <ciso646>
# include <clocale>
# include <csetjmp>
# include <csignal>
# include <cstdbool>
# include <cinttypes>
# include <charconv>
# include <typeindex>
# include <any>
# include <scoped_allocator>
# include <forward_list>
# include <list>
# include <map>
# include <set>
# include <valarray>
# include <variant>
# include <unordered_map>
# include <unordered_set>
# include <queue>
# include <condition_variable>
# include <shared_mutex>
# include <codecvt>
# include <future>
# include <regex>
# include <iostream>
# include <random>
# include <ctgmath>
# include <fstream>
#endif // <bits/stdc++.h>
/// abi
#if __has_include(<cxxabi.h>)
# define INCLUDED_CXXABI
# include <cxxabi.h>
#endif // <cxxabi.h>
// boost libraries
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
# define INCLUDED_BOOST_CPP_INT
# include <boost/multiprecision/cpp_int.hpp>
#endif
#if __has_include(<boost/math/special_functions/prime.hpp>)
# define INCLUDED_BOOST_PRIME
# include <boost/math/special_functions/prime.hpp>
#endif
#if __has_include(<boost/multiprecision/miller_rabin.hpp>)
# define INCLUDED_BOOST_MILLER_RABIN
# include <boost/multiprecision/miller_rabin.hpp>
#endif
// atcoder libraries
#if __has_include(<atcoder/all>)
# define INCLUDED_ACL
# include <atcoder/all>
#endif
/// sfinae
// is_pair
template <typename T> inline constexpr bool is_pair_v = false;
template <typename T, typename U> inline constexpr bool is_pair_v<std::pair<T, U>> = true;
// is_tuple
template <typename T> inline constexpr bool is_tuple_v = false;
template <typename... Types> inline constexpr bool is_tuple_v<std::tuple<Types...>> = true;
// istreamable
#if __cplusplus >= 202002L
template <typename T> concept istreamable_v = requires (T a) { std::cin >> a; };
#else // C++20
template<typename T, typename = void> inline constexpr bool istreamable_v = false;
template<typename T>
inline constexpr bool istreamable_v<T, std::void_t<decltype(std::cin >> std::declval<T&>())>> = true;
#endif // C++20
// ostreamable
#if __cplusplus >= 202002L
template <typename T> concept ostreamable_v = requires (T a) { std::cout << a; };
#else // C++20
template<typename T, typename = void> inline constexpr bool ostreamable_v = false;
template<typename T>
inline constexpr bool ostreamable_v<T, std::void_t<decltype(std::cout << std::declval<T&>())>> = true;
#endif // C++20
// iterable
#if __cplusplus >= 202002L
# if __has_include(<ranges>)
template <typename T> concept iterable_v = std::ranges::range<T>;
# else // <ranges>
template <typename T> concept iterable_v = requires (T a) { std::begin(a); std::end(a); };
# endif // C++20
#else // C++20
template <typename T> inline constexpr bool iterable_v =
std::is_same_v<decltype(std::begin(std::declval<T>())), decltype(std::end(std::declval<T>()))>;
#endif // C++20
/// utils
template <typename T> inline std::string get_typename(std::size_t length_limit = std::string::npos) {
std::string name;
#ifdef INCLUDED_CXXABI
name = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, nullptr);
#else // INCLUDED_CXXABI
name = typeid(T).name();
#endif // INCLUDED_CXXABI
#ifdef __ANDROID__
name = std::regex_replace(name, std::regex("::__ndk1::"), "::");
#endif // __ANDROID__
if (name.length() > length_limit) name = name.substr(0, length_limit - 3) + "...";
return name;
}
template <typename T> constexpr T inf() {
if constexpr (std::numeric_limits<T>::has_infinity) return std::numeric_limits<T>::infinity();
return std::numeric_limits<T>::max() / 2.125L;
}
template <typename T> constexpr int sin90(T theta90) {
if (theta90 % 2 == 0) return 0;
return (theta90 % 4 + 4) % 4 < 2 ? 1 : -1;
}
template <typename T> constexpr int cos90(T theta90) {
return sin90(theta90 + 1);
}
template <typename T> constexpr int sin45(T theta45) {
if (theta45 % 4 == 0) return 0;
return (theta45 % 8 + 8) % 8 < 4 ? 1 : -1;
}
template <typename T> constexpr int cos45(T theta45) {
return sin45(theta45 + 2);
}
template <typename T, typename U> inline bool chmin(T &&a, const U b) {
const bool compare = a > b;
if (compare) a = b;
return compare;
}
template <typename T, typename U> inline bool chmax(T &&a, const U b) {
const bool compare = a < b;
if (compare) a = b;
return compare;
}
long long powi(int base, int exponent = 2) {
long long ans = 1;
for (int i = exponent; i != 0; i += (i >= 0 ? -1 : 1)) {
if (i >= 0) ans *= base;
else ans /= base;
if (ans == 0) break;
}
return ans;
}
#ifdef INCLUDED_ACL
template <typename T = atcoder::modint>
T mint_inv(T x) {
constexpr int memo_limit = 1 << 24;
static std::array<T, memo_limit> memo;
if (x.val() >= memo_limit) return x.inv();
if (memo[x.val()] == 0) memo[x.val()] = x.inv();
return memo[x.val()];
}
#endif // INCLUDED_ACL
template <typename T> bool is_prime(T n) {
if (n <= 1) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
// miller rabin
#ifdef INCLUDED_ACL
if (n <= std::min(1LL << 32, static_cast<long long>(std::numeric_limits<int>::max()))) {
return atcoder::internal::is_prime_constexpr(n);
}
#endif // INCLUDED_ACL
#ifdef INCLUDED_BOOST_MILLER_RABIN
return boost::multiprecision::miller_rabin_test(n, 25);
#endif // INCLUDED_BOOST_MILLER_RABIN
// binary search
#ifdef INCLUDED_BOOST_PRIME
if (n <= boost::math::prime(boost::math::max_prime)) {
int left = 0, right = boost::math::max_prime + 1;
while (right - left > 1) {
auto mid = (left + right) / 2;
(boost::math::prime(mid) <= n ? left : right) = mid;
}
return n == boost::math::prime(left);
}
#endif // INCLUDED_BOOST_PRIME
// trial
T tried = 3;
#ifdef INCLUDED_BOOST_PRIME
for (int i = 2; i <= int(boost::math::max_prime); ++i) {
const auto prime_i = boost::math::prime(i);
if (prime_i > n / prime_i) return true;
if (n % prime_i == 0) return false;
tried = prime_i;
}
#endif // INCLUDED_BOOST_PRIME
for (T i = (tried + 5) / 6 * 6; (i - 1) * (i - 1) <= n; i += 6) {
if (n % (i - 1) == 0 || n % (i + 1) == 0) return false;
}
return true;
}
// thanks to https://perogram.hateblo.jp/entry/2019/03/29/193632
template <bool osa_k = false, typename T> std::vector<std::pair<T, int>> factors(T n) {
constexpr int spf_limit = 1 << 24;
std::vector<std::pair<T, int>> result;
if (n < 0) {
result.emplace_back(-1, 1);
const auto natural = factors<osa_k>(-n);
result.insert(result.end(), natural.begin(), natural.end());
} else if (n == 0) result.emplace_back(0, 1);
else if (n == 1);
else if (osa_k && n < spf_limit) {
static std::array<int, spf_limit> spf;
if (spf[0] == 0) {
for (int i = 0; i < spf_limit; ++i) spf[i] = i % 2 == 0 ? 2 : i % 3 == 0 ? 3 : i;
spf[0] = 1;
for (int p1 = 6; (p1 - 1) * (p1 - 1) <= spf_limit; p1 += 6) {
if (spf[p1 - 1] == p1 - 1) for (int i = p1 - 1; i < spf_limit; i += p1 - 1) if (spf[i] == i) spf[i] = p1 - 1;
if (spf[p1 + 1] == p1 + 1) for (int i = p1 + 1; i < spf_limit; i += p1 + 1) if (spf[i] == i) spf[i] = p1 + 1;
}
}
while (n != 1) {
if (!result.empty() && result.back().first == spf[n]) ++result.back().second;
else result.emplace_back(spf[n], 1);
n /= spf[n];
}
} else {
int expo = 0;
while (n % 2 == 0) { n /= 2; ++expo; }
if (expo != 0) result.emplace_back(2, expo);
expo = 0;
while (n % 3 == 0) { n /= 3; ++expo; }
if (expo != 0) result.emplace_back(3, expo);
T tried = 3;
#ifdef INCLUDED_BOOST_PRIME
for (int i = 2; i <= int(boost::math::max_prime); ++i) {
const auto prime_i = boost::math::prime(i);
if (prime_i > n / prime_i) break;
expo = 0;
while (n % prime_i == 0) { n /= prime_i; ++expo; }
result.emplace_back(prime_i, expo);
tried = prime_i;
}
if (osa_k && n < spf_limit) {
const auto rest = factors<osa_k>(n);
result.insert(result.end(), rest.begin(), rest.end());
n = 1;
}
#endif // INCLUDED_BOOST_PRIME
if (is_prime(n)) { result.emplace_back(n, 1); n = 1; }
for (T i = (tried + 5) / 6 * 6; (i - 1) * (i - 1) <= n; i += 6) {
expo = 0;
while (n % (i - 1) == 0) { n /= (i - 1); ++expo; }
if (expo != 0) result.emplace_back(i - 1, expo);
expo = 0;
while (n % (i + 1) == 0) { n /= (i + 1); ++expo; }
if (expo != 0) result.emplace_back(i + 1, expo);
if (osa_k && n < spf_limit) {
const auto rest = factors<osa_k>(n);
result.insert(result.end(), rest.begin(), rest.end());
n = 1;
}
}
if (n != 1) result.emplace_back(n, 1);
}
return result;
}
template <bool osa_k = false, typename T> std::vector<T> divisors(T n, bool sorted = true) {
std::vector<T> result(1, 1);
for (auto [prime, expo] : factors<osa_k>(n)) {
const int result_size = result.size();
T pow_i = 1;
for (int i = 1; i <= expo; ++i) {
pow_i *= prime;
for (int k = 0; k < result_size; ++k) result.emplace_back(result[k] * pow_i);
}
}
if (sorted) std::sort(result.begin(), result.end());
return result;
}
template <typename T> T fact(int n, bool inv = false) {
assert(n >= 0);
static std::vector<std::pair<T, T>> factorials = { { 1, 1 } };
for (int i = factorials.size(); i <= n; ++i) factorials.emplace_back(i * factorials[i - 1].first, 0);
if (inv && factorials[n].second == 0) {
if constexpr (std::is_integral_v<T>) factorials[n].second = factorials[n].first <= 1 ? 1 : 0;
#ifdef INCLUDED_ACL
else if constexpr (atcoder::internal::is_modint<T>::value) factorials[n].second = mint_inv(factorials[n].first);
#endif // INCLUDED_ACL
else factorials[n].second = 1 / factorials[n].first;
}
return inv ? factorials[n].second : factorials[n].first;
}
template <typename T> T perm(int n, int k) { return fact<T>(n) * fact<T>(n - k, true); }
template <typename T> T comb(int n, int k) { return perm<T>(n, k) * fact<T>(k, true); }
// TODO: compressor
/*template <typename T> struct compressor {
std::vector<T> positions;
compressor() = default;
compressor(const std::vector<T> &initial_pos) {
}
};*/
template <typename T> std::vector<std::vector<T>> rotate(std::vector<std::vector<T>> grid, int angle = 1) {
angle %= 4;
if (angle == 0) return grid;
auto h = grid.size(), w = grid[0].size();
auto rotated = std::vector(w, std::vector<T>(h));
for (int y = 0; y < h; ++y) for (int x = 0; x < w; ++x) rotated[w - 1 - x][y] = grid[y][x];
return rotate(rotated, angle - 1);
}
std::string int128_to_str(__int128_t target) {
std::string target_str;
__uint128_t target_tmp = target < 0 ? -target : target;
do {
target_str += '0' + target_tmp % 10;
target_tmp /= 10;
} while (target_tmp != 0);
if (target < 0) target_str += '-';
std::reverse(target_str.begin(), target_str.end());
return target_str;
}
template <typename T> std::string to_pretty_str(T target) {
using namespace std;
string str;
if constexpr (is_void_v<T>) str += "void"s;
else if constexpr (is_null_pointer_v<T>) str += "null"s;
else if constexpr (is_same_v<T, bool>) str += target ? "true"s : "false"s;
else if constexpr (is_same_v<T, char> || is_same_v<T, char16_t> || is_same_v<T, char32_t> || is_same_v<T, wchar_t>) {
str += "'"s + target + "'"s;
#ifdef INCLUDED_ACL
} else if constexpr (atcoder::internal::is_modint<T>::value) {
str += to_string(target.val()) + "(mod)"s;
#endif // INCLUDED_ACL
} else if constexpr (is_arithmetic_v<T>) {
if constexpr (is_same_v<T, __int128_t>) str += int128_to_str(target);
else str += to_string(target);
if constexpr (is_unsigned_v<T>) str += "u"s;
if constexpr (is_same_v<remove_cv_t<T>, long>) str += "L"s;
else if constexpr (is_same_v<remove_cv_t<T>, long long>) str += "LL"s;
else if constexpr (is_same_v<T, __int128_t>) str += "LLL"s;
} else if constexpr (is_pair_v<T>) {
str += "("s + to_pretty_str(target.first);
str += ", "s + to_pretty_str(target.second) + ")"s;
} else if constexpr (is_convertible_v<T, string>) {
str += "\""s + target + "\""s;
} else if constexpr (is_array_v<T>) {
str += "["s;
bool separate = false;
for (const auto &target_i : target) {
if (separate) str += ", "s;
str += to_pretty_str(target_i);
separate = true;
}
str += "]"s;
} else if constexpr (iterable_v<T>) {
str += "("s + get_typename<T>(20) + "){"s;
bool separate = false;
for (const auto &target_i : target) {
if (separate) str += ","s;
str += " "s + to_pretty_str(target_i);
separate = true;
}
if (separate) str += " "s;
str += "}"s;
} else {
str += "<"s + get_typename<T>(20);
str += " ("s + to_string(sizeof(target)) + " byte)>"s;
}
return str;
}
// input
#ifdef DEBUG
std::chrono::milliseconds input_total_ms{0};
#endif // DEBUG
template <typename T> inline void read_stdin(T &&target) {
#ifdef DEBUG
using namespace std::chrono;
const auto start = system_clock::now();
std::cin >> target;
const auto end = system_clock::now();
input_total_ms += duration_cast<milliseconds>(end - start);
#else // DEBUG
std::cin >> target;
#endif // DEBUG
}
template <typename T> inline T input(T &&target) {
using T_V = std::remove_reference_t<T>;
if constexpr (istreamable_v<T_V>) read_stdin(target);
else if constexpr (iterable_v<T_V>) for (auto &&target_i : target) input(target_i);
else if constexpr (is_pair_v<T_V>) {
input(target.first);
input(target.second);
} else if constexpr (std::is_convertible_v<long long, T_V>) {
long long n;
target = input(n);
} else {
#ifdef DEBUG
std::cerr << "[WARN] Type " << get_typename<T_V>()
<< " is invalid, so input is skipped;" << std::endl;
#endif //DEBUG
}
return target;
}
// input and initialize
struct Scanner { template <typename T> inline operator T() const { T target; return input(target); } } scan;
// output
template <typename T> inline void write_stdout(T target, bool flush = false) {
std::cout << target;
if (flush) std::cout << std::flush;
}
template <typename T, typename Sep = char> inline void output(T target, Sep separator = ' ', bool flush = false) {
if constexpr (ostreamable_v<T>) {
write_stdout(target, flush);
} else if constexpr (std::is_convertible<T, __int128_t>::value) {
write_stdout(int128_to_str(target), flush);
# ifdef INCLUDED_ACL
} else if constexpr (atcoder::internal::is_modint<T>::value) {
output(target.val(), separator, flush);
# endif // INCLUDED_ACL
} else if constexpr (iterable_v<T>) {
bool separate = false;
for (const auto target_i : target) {
if (separate) write_stdout(separator);
output(target_i, separator);
separate = true;
}
if (flush) write_stdout("", flush);
} else if constexpr (is_pair_v<T>) {
output(target.first, separator);
write_stdout(separator);
output(target.second, separator, flush);
} else {
write_stdout("<unknown>", flush);
}
}
template <typename T, typename Sep = char> inline void outputln(T target, Sep separator = ' ', bool flush = false) {
output(target, separator);
write_stdout('\n', flush);
}
// debug output
#ifdef DEBUG
std::chrono::milliseconds debug_total_ms{0};
template <typename F> void debug_txt_f(F callback, int line = -1, std::string file = (__FILE__)) {
using namespace std::chrono;
const auto start = system_clock::now();
std::string dump_str = "[DEBUG] ";
if (line >= 0) {
dump_str += "(";
if (file != (__FILE__)) dump_str += file + ":";
dump_str += "L" + std::to_string(line) + ") ";
}
dump_str += callback();
std::cerr << dump_str << std::endl;
const auto end = system_clock::now();
debug_total_ms += duration_cast<milliseconds>(end - start);
}
# define debug_txt(txt) (debug_txt_f([]() { return to_pretty_str(txt); }, (__LINE__), (__FILE__)), true)
template <typename... Types>
void dump_f(std::string labels, std::tuple<Types...> targets_tupl, int line = -1, std::string file = (__FILE__)) {
debug_txt_f([=]() {
std::string txt;
std::apply([labels, &txt](auto... targets) {
int i = 0, label_left = 0;
(([&](auto target) {
const auto label_len = labels.find(',', label_left) - label_left;
const auto label =
std::regex_replace(labels.substr(label_left, label_len),
std::regex("^\\s+|\\s+$"), "");
if (i >= 1) txt += ", ";
txt += label + ": " + to_pretty_str(target);
label_left += label_len + 1;
++i;
})(targets), ...);
txt += ";";
}, targets_tupl);
return txt;
}, line, file);
}
# define dump(...) (dump_f((#__VA_ARGS__), std::make_tuple(__VA_ARGS__), (__LINE__), (__FILE__)), true)
void dump_canvas_f(std::string label, std::vector<std::string> canvas, int line = -1, std::string file = (__FILE__)) {
debug_txt_f([=]() {
int h = canvas.size(), w = canvas[0].size();
std::string txt = label + " (" + std::to_string(h) + " x " + std::to_string(w) + ")\n";
std::string ruler0(w, ' '), ruler1(w, '-');
for (int x = 0; x < w; x += 4) {
auto x_s = std::to_string(x);
for (std::size_t i = 0; i < x_s.size(); ++i) ruler0[x - i] = x_s[x_s.size() - i - 1];
ruler1[x] = '+';
}
txt += " |" + ruler0 + "\n---+" + ruler1;
for (int y = 0; y < h; ++y) {
std::string ruler = " |";
if (y % 4 == 0) {
auto y_s = std::to_string(y);
for (std::size_t i = 0; i < y_s.size(); ++i) ruler[2 - i] = y_s[y_s.size() - i - 1];
ruler[3] = '+';
}
txt += "\n" + ruler + canvas[y];
}
return txt;
}, line, file);
}
# define dump_canvas(canvas) (dump_canvas_f((#canvas), (canvas), (__LINE__), (__FILE__)), true)
// TODO: dump_table
#else // DEBUG
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-value"
# define debug_txt(...) (false)
# define dump(...) (false)
# define dump_canvas(...) (false)
# pragma GCC diagnostic pop
#endif // DEBUG
/// main
#if !defined(__INCLUDE_LEVEL__) || __INCLUDE_LEVEL__ <= 1
inline std::string cp_main();
int main() {
using namespace std;
# ifdef DEBUG
using namespace std::chrono;
cerr << "[INFO] running in debug mode!" << endl;
const auto start = system_clock::now();
try {
# endif // DEBUG
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(12);
// run!!!
const auto result = cp_main();
if (!result.empty()) write_stdout(result);
# ifdef DEBUG
write_stdout('\n', true);
} catch (exception &e) {
write_stdout('\n', true);
cerr << "[ERROR] " << e.what() << endl;
}
const auto end = system_clock::now();
const auto time_ms = duration_cast<milliseconds>(end - start) - input_total_ms - debug_total_ms;
cerr << "[INFO] finished in " << time_ms.count() << " ms!" << endl;
# endif // DEBUG
return 0;
}
#endif // __INCLUDE_LEVEL__
/// aliases
using i32 = int; using u32 = unsigned int;
using i64 = long long; using u64 = unsigned long long;
using i128 = __int128; using u128 = unsigned __int128;
using f32 = float; using f64 = double; using f80 = long double;
using str = std::string;
template <typename T> using vec = std::vector<T>;
template <typename T, typename Compare = std::less<T>> using p_que = std::priority_queue<T, std::vector<T>, Compare>;
template <typename Key, typename Compare = std::less<Key>> using mset = std::multiset<Key, Compare>;
template <typename Key, typename T, typename Compare = std::less<Key>> using mmap = std::multimap<Key, T, Compare>;
template <typename Key> using u_set = std::unordered_set<Key>;
template <typename Key> using u_mset = std::unordered_multiset<Key>;
template <typename Key, typename T> using u_map = std::unordered_map<Key, T>;
template <typename Key, typename T> using u_mmap = std::unordered_multimap<Key, T>;
#ifdef INCLUDED_BOOST_CPP_INT
using bigint = boost::multiprecision::cpp_int;
#endif // INCLUDED_BOOST_CPP_INT
using namespace std;
#if __cplusplus >= 202002L && __has_include(<ranges>)
namespace rng = std::ranges;
namespace viw = std::ranges::views;
#endif // C++20 && <ranges>
#ifdef INCLUDED_ACL
using namespace atcoder;
#endif // INCLUDED_ACL
#pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-variable"
constexpr auto infi = inf<int>();
constexpr auto infl = inf<long long>();
constexpr auto infd = inf<double>();
constexpr auto infld = inf<long double>();
const std::array YN = { "No"s, "Yes"s };
const std::array AB = { "Bob"s, "Alice"s };
const std::array FS = { "Second"s, "First"s };
const std::array TA = { "Aoki"s, "Takahashi"s };
#pragma GCC diagnostic pop
// functions
#define tostr to_string
#define dist distance
#define min_e min_element
#define max_e max_element
#define iota_v iota_view
#define p1 first
#define p2 second
#define has contains
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
// cast
#define sz(x) (int(std::ssize(x)))
#define bit_width(x) (int(std::bit_width(x)))
// repeat
#define reps(i, l, r) for (std::decay_t<decltype(r)> i##_right = (r), i = (l); i < i##_right; ++i)
#define rep(i, n) reps(i, 0, n)
#define rreps(i, l, r) for (std::decay_t<decltype(r)> i##_left = (l), i = (r) - 1; i >= i##_left; --i)
#define rrep(i, n) rreps(i, 0, n)
#define each(for_able) for (auto &&for_able##_i : (for_able))
// iterate
#define all(for_able) (std::begin(for_able)), (std::end(for_able))
#define rev(for_able) (std::rbegin(for_able)), (std::rend(for_able))
// lambda
#define pred(x, expr) ([&](auto &&x) -> bool { return (expr); })
#define comp(x, y, expr) ([&](auto &&x, auto &&y) -> bool { return (expr); })
/// answer
#line 2 "fps/count_increasing_sequences.hpp"
#include <atcoder/convolution>
#line 2 "math/Binomial.hpp"
#include<vector>
#include<assert.h>
namespace po167{
template<class T>
struct Binomial{
std::vector<T> fact_vec, fact_inv_vec;
void extend(int m = -1){
int n = fact_vec.size();
if (m == -1) m = n * 2;
if (n >= m) return;
fact_vec.resize(m);
fact_inv_vec.resize(m);
for (int i = n; i < m; i++){
fact_vec[i] = fact_vec[i - 1] * T(i);
}
fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
for (int i = m - 1; i > n; i--){
fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
}
}
Binomial(int MAX = 0){
fact_vec.resize(1, T(1));
fact_inv_vec.resize(1, T(1));
extend(MAX + 1);
}
T fact(int i){
if (i < 0) return 0;
while (int(fact_vec.size()) <= i) extend();
return fact_vec[i];
}
T invfact(int i){
if (i < 0) return 0;
while (int(fact_inv_vec.size()) <= i) extend();
return fact_inv_vec[i];
}
T C(int a, int b){
if (a < b || b < 0) return 0;
return fact(a) * invfact(b) * invfact(a - b);
}
T invC(int a, int b){
if (a < b || b < 0) return 0;
return fact(b) * fact(a - b) *invfact(a);
}
T P(int a, int b){
if (a < b || b < 0) return 0;
return fact(a) * invfact(a - b);
}
T inv(int a){
if (a < 0) return inv(-a) * T(-1);
if (a == 0) return 1;
return fact(a - 1) * invfact(a);
}
T Catalan(int n){
if (n < 0) return 0;
return fact(2 * n) * invfact(n + 1) * invfact(n);
}
T narayana(int n, int k){
if (n <= 0 || n < k || k < 1) return 0;
return C(n, k) * C(n, k - 1) * inv(n);
}
T Catalan_pow(int n,int d){
if (n < 0 || d < 0) return 0;
if (d == 0){
if (n == 0) return 1;
return 0;
}
return T(d) * inv(d + n) * C(2 * n + d - 1, n);
}
// retrun [x^a] 1/(1-x)^b
T ruiseki(int a,int b){
if (a < 0 || b < 0) return 0;
if (a == 0){
return 1;
}
return C(a + b - 1, b - 1);
}
// (a, b) -> (c, d)
// always x + e >= y
T mirror(int a, int b, int c, int d, int e = 0){
if (a + e < b || c + e < d) return 0;
if (a > c || b > d) return 0;
a += e;
c += e;
return C(c + d - a - b, c - a) - C(c + d - a - b, c - b + 1);
}
// return sum_{i = 0, ... , a} sum_{j = 0, ... , b} C(i + j, i)
// return C(a + b + 2, a + 1) - 1;
T gird_sum(int a, int b){
if (a < 0 || b < 0) return 0;
return C(a + b + 2, a + 1) - 1;
}
// return sum_{i = a, ..., b - 1} sum_{j = c, ... , d - 1} C(i + j, i)
// AGC 018 E
T gird_sum_2(int a, int b, int c, int d){
if (a >= b || c >= d) return 0;
a--, b--, c--, d--;
return gird_sum(a, c) - gird_sum(a, d) - gird_sum(b, c) + gird_sum(b, d);
}
// the number of diagonal dissections of a convex n-gon into k+1 regions.
// OEIS A033282
// AGC065D
T diagonal(int n, int k){
if (n <= 2 || n - 3 < k || k < 0) return 0;
return C(n - 3, k) * C(n + k - 1, k) * inv(k + 1);
}
};
}
#line 4 "fps/FPS_cyclic_convolution.hpp"
namespace po167{
// |f| = |g| = 2 ^ n
template<class T>
std::vector<T> FPS_cyclic_convolution(std::vector<T> f, std::vector<T> g){
atcoder::internal::butterfly(f);
atcoder::internal::butterfly(g);
for (int i = 0; i < (int)f.size(); i++) f[i] *= g[i];
atcoder::internal::butterfly_inv(f);
T iz = (T)(1) / (T)(f.size());
for (int i = 0; i < (int)f.size(); i++) f[i] *= iz;
return f;
}
}
#line 5 "fps/count_increasing_sequences.hpp"
namespace po167{
template<class T>
std::pair<std::vector<T>, std::vector<T>> count_square(std::vector<T> L, std::vector<T> D){
assert(!L.empty() && !D.empty());
int N = L.size();
int M = D.size();
if (std::min(N, M) <= 400){
int sw = 0;
if (N > M) std::swap(N, M), std::swap(L, D), sw = 1;
std::vector<T> R(N);
for (int i = 0; i < N; i++){
D[0] += L[i];
for (int j = 1; j < M; j++) D[j] += D[j - 1];
R[i] = D.back();
}
if (sw) std::swap(R, D);
return {R, D};
}
po167::Binomial<T> table(N + M);
std::vector<T> R(N), U(M);
int z = 0;
while ((1 << z) < (N + M - 1)) z++;
// 左から右
{
std::vector<T> tmp(N);
for (int i = 0; i < N; i++) tmp[i] = table.C(M - 1 + i, i);
tmp = atcoder::convolution(tmp, L);
for (int i = 0; i < N; i++) R[i] += tmp[i];
}
// 左から上
{
std::vector<T> tmp(1 << z);
for (int i = 0; i < N; i++) L[i] *= table.invfact(N - 1 - i);
for (int i = 0; i < N + M - 1; i++) tmp[i] = table.fact(i);
L.resize(1 << z, 0);
tmp = po167::FPS_cyclic_convolution(tmp, L);
for (int i = 0; i < M; i++) U[i] += tmp[N - 1 + i] * table.invfact(i);
}
// 下から上
{
std::vector<T> tmp(M);
for (int i = 0; i < M; i++) tmp[i] = table.C(N - 1 + i, i);
tmp = atcoder::convolution(tmp, D);
for (int i = 0; i < M; i++) U[i] += tmp[i];
}
// 下から右
{
std::vector<T> tmp(1 << z);
for (int i = 0; i < M; i++) D[i] *= table.invfact(M - i - 1);
for (int i = 0; i < N + M - 1; i++) tmp[i] = table.fact(i);
D.resize(1 << z, 0);
tmp = po167::FPS_cyclic_convolution(tmp, D);
for (int i = 0; i < N; i++) R[i] += tmp[M - 1 + i] * table.invfact(i);
}
return {R, U};
}
template<class T>
/*
* g(A, x) を
* 0 <= B[i] < A[i] かつ B[i] = x を満たす
* 広義単調増加列 B の数とする
* res[x] = sum C[i] * g(A[i:N], x)
* を返す
*/
std::vector<T> count_increase_sequences_with_upper_bounds(std::vector<int> A, std::vector<T> C){
int N = A.size();
assert((int)C.size() == N);
assert(N);
for (int i = (int)(A.size()) - 1; i > 0; i--) A[i - 1] = std::min(A[i - 1], A[i]);
if (A.back() == 0) return {};
if (std::min(A.back(), N) <= 400){
std::vector<T> dp(0);
dp.reserve(A.back());
for (int i = 0; i < N; i++){
dp.resize(A[i], 0);
if (A[i]) dp[0] += C[i];
for (int j = 1; j < (int)dp.size(); j++){
dp[j] += dp[j - 1];
}
}
return dp;
}
if (N == 1){
std::vector<T> res(A[0]);
for (int i = 0; i < A[0]; i++) res[i] = C[0];
return res;
}
int m = N / 2;
std::vector<int> LA(m), RA(N - m);
std::vector<T> LC(m), RC(N - m);
for (int i = 0; i < m; i++){
LA[i] = A[i];
LC[i] = C[i];
}
for (int i = 0; i < N - m; i++){
RA[i] = A[i + m] - A[m - 1];
RC[i] = C[i + m];
}
std::vector<T> res;
res.reserve(A.back());
auto L = count_increase_sequences_with_upper_bounds(LA, LC);
if (!L.empty()){
auto [R, U] = count_square(L, RC);
for (int i = 0; i < (int)R.size(); i++) res.push_back(R[i]);
std::swap(U, RC);
}
auto R = count_increase_sequences_with_upper_bounds(RA, RC);
for (auto x : R) res.push_back(x);
return res;
}
template<class T>
/*
* f(a, b) を X[0] = a, X[N - 1] = b であるような、A, B に挟まれたものとする
* 長さ B[N - 1] - A[N - 1] を返す
* res[b - A.back()] = sum C[a - A[0]] * f(a, b)
* A, B は広義単調増加が嬉しい
* C は空ならば、全て 1 であるとする。
* そうでないなら、|C| = B[0] - A[0] でないといけない
*/
std::vector<T> count_increase_sequences_with_upper_lower_bounds(std::vector<int> A, std::vector<int> B, std::vector<T> C = {}){
int N = A.size();
assert(A.size() == B.size());
for (int i = 0; i < N - 1; i++){
A[i + 1] = std::max(A[i], A[i + 1]);
}
for (int i = N - 1; i > 0; i--){
B[i - 1] = std::min(B[i], B[i - 1]);
}
if (A.back() >= B.back()) return {};
// A[0] == 0 にする
std::vector<T> res(B.back() - A.back(), 0);
{
int tmp = A[0];
for (int i = 0; i < N; i++){
A[i] -= tmp;
B[i] -= tmp;
if (A[i] >= B[i]) return res;
}
}
if (C.empty()){
C.resize(B[0] - A[0], 1);
}
else assert((int)(C.size()) == B[0] - A[0]);
int l = 0;
while (B[l] <= A.back()){
for (int i = (int)(C.size()) - 1; i > 0; i--) C[i] -= C[i - 1];
int nl = l;
while (A[nl] < B[l]) nl++;
std::vector<int> tmp(B[l] - A[l]);
tmp[0] = 1;
for (int i = l; i < nl; i++){
tmp[A[i] - A[l]]++;
}
for (int i = 1; i < B[l] - A[l]; i++) tmp[i] += tmp[i - 1];
auto X = count_increase_sequences_with_upper_bounds(tmp, C);
std::vector<int> nB(nl - l + 1);
for (int i = l; i <= nl; i++){
nB[i - l] = B[i] - B[l];
}
auto Y = count_increase_sequences_with_upper_bounds(nB, X);
C.resize(B[nl] - A[nl]);
for (int i = 0; i < B[nl] - A[nl]; i++){
C[i] = Y[i + A[nl] - B[l]];
}
l = nl;
}
// A を揃えてしまえ
{
int a = A[l];
for (int i = l; i < N; i++){
A[i] -= a;
B[i] -= a;
}
}
for (int i = (int)(C.size()) - 1; i > 0; i--) C[i] -= C[i - 1];
std::vector<T> D(N - l, 0);
if (A.back() != 0){
std::vector<T> L(A.back());
for (int i = 0; i < (int)L.size(); i++) L[i] = C[i];
std::vector<int> tmp(L.size());
tmp[0] = 1;
for (int i = l; i < N; i++){
if (A[i] < (int)tmp.size()) tmp[A[i]]++;
}
for (int i = 1; i < (int)tmp.size(); i++){
tmp[i] += tmp[i - 1];
}
auto nD = count_increase_sequences_with_upper_bounds(tmp, L);
for (int i = 0; i < (int)nD.size(); i++) D[i] = nD[i];
}
for (int i = A.back(); i < B[l]; i++) C[i - A.back()] = C[i];
C.resize(B[l] - A.back());
auto [R, U] = count_square(C, D);
res = R;
std::vector<int> nB(N - l);
for (int i = 0; i < N - l; i++) nB[i] = B[i + l] - B[l];
R = count_increase_sequences_with_upper_bounds(nB, U);
for (auto x : R) res.push_back(x);
return res;
}
}
#line 994 "main.cc"
using mint=modint998244353;
inline str cp_main() {
str s=scan;
auto a=vec<int>{};
rep(i,sz(s)) {
if (s[i]=='A') a.eb(i+1);
}
auto tmp=po167::count_increase_sequences_with_upper_lower_bounds<mint>(vec(sz(a),0),a);
outputln(accumulate(all(tmp),mint(0)));
return "";
}