This documentation is automatically generated by online-judge-tools/verification-helper
// verification-helper: PROBLEM https://atcoder.jp/contests/arc117/tasks/arc117_c
#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/modular-arithmetic/small-mod-combination.hpp"
#include "src/math/modular-arithmetic/static-modint.hpp"
#include <iostream>
#include <string>
namespace luz {
void main_() {
using mint = StaticPrimeModInt< 3 >;
SmallModCombination< mint > mc;
usize n;
std::cin >> n;
std::string s;
std::cin >> s;
auto convert = [](char c) {
switch (c) {
case 'B':
return 0;
case 'W':
return 1;
case 'R':
return 2;
default:
exit(-1);
}
};
mint sum;
for (usize i = 0; i < n; i++) {
sum +=
(n & 1 ? 1 : -1) * convert(s[i]) * mc.combination(n - 1, i);
}
auto inverse = [](mint x) {
switch (x.val()) {
case 0:
return 'B';
case 1:
return 'W';
case 2:
return 'R';
default:
exit(-1);
}
};
std::cout << inverse(sum) << std::endl;
}
} // namespace luz
int main() {
luz::main_();
}
#line 1 "test/atcoder/arc117_c.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/arc117/tasks/arc117_c
#line 2 "src/cpp-template/header/size-alias.hpp"
#include <cstddef>
namespace luz {
using isize = std::ptrdiff_t;
using usize = std::size_t;
} // namespace luz
#line 2 "src/math/modular-arithmetic/small-mod-combination.hpp"
#line 2 "src/cpp-template/header/int-alias.hpp"
#include <cstdint>
namespace luz {
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
} // namespace luz
#line 2 "src/math/modular-arithmetic/modular-combinatorics.hpp"
#line 2 "src/cpp-template/header/rep.hpp"
#line 4 "src/cpp-template/header/rep.hpp"
#include <algorithm>
namespace luz {
struct rep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
++i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rep(const usize f, const usize l) noexcept
: f(std::min(f, l)),
l(l) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
struct rrep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
--i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rrep(const usize f, const usize l) noexcept
: f(l - 1),
l(std::min(f, l) - 1) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
} // namespace luz
#line 5 "src/math/modular-arithmetic/modular-combinatorics.hpp"
#include <vector>
namespace luz {
template < typename mint >
class Combinatorics {
static usize bound;
static std::vector< mint > fact, finv, inv;
static void expand(usize n) {
n += 1;
if (fact.size() >= n) return;
if (bound == 0) bound = 1;
fact.resize(n, mint(1));
finv.resize(n, mint(1));
inv.resize(n, mint(1));
for (usize i: rep(bound, n)) {
fact[i] = fact[i - 1] * i;
}
finv.back() = mint(1) / fact.back();
for (usize i: rrep(bound, n)) {
finv[i - 1] = finv[i] * i;
}
for (usize i: rep(bound, n)) {
inv[i] = finv[i] * fact[i - 1];
}
bound = n;
}
public:
explicit Combinatorics(usize n = 0) {
expand(n);
}
static mint factorial(usize n) {
expand(n);
return fact[n];
}
static mint factorial_inverse(usize n) {
expand(n);
return finv[n];
}
static mint inverse(usize n) {
expand(n);
return inv[n];
}
static mint permutation(isize n, isize r) {
if (r < 0 or n < r) return 0;
expand(n);
return fact[n] * finv[n - r];
}
static mint combination(isize n, isize r) {
if (r < 0 or n < r) return 0;
expand(n);
return fact[n] * finv[r] * finv[n - r];
}
static mint combination_with_repetitions(isize n, isize r) {
if (n < 0 or r < 0) return 0;
return (r ? combination(n + r - 1, r) : 1);
}
static mint P(isize n, isize r) {
return permutation(n, r);
}
static mint C(isize n, isize r) {
return combination(n, r);
}
static mint H(isize n, isize r) {
return combination_with_repetitions(n, r);
}
};
template < typename mint >
usize Combinatorics< mint >::bound = 0;
template < typename mint >
std::vector< mint > Combinatorics< mint >::fact =
std::vector< mint >();
template < typename mint >
std::vector< mint > Combinatorics< mint >::finv =
std::vector< mint >();
template < typename mint >
std::vector< mint > Combinatorics< mint >::inv =
std::vector< mint >();
} // namespace luz
#line 6 "src/math/modular-arithmetic/small-mod-combination.hpp"
namespace luz {
template < typename modint >
class SmallModCombination {
static constexpr u32 mod = modint::get_mod();
Combinatorics< modint > mc;
public:
SmallModCombination(): mc(mod - 1) {}
modint combination(isize n, isize r) {
if (r < 0 or n < r) return 0;
modint result(1);
while (n) {
result *= mc.combination(n % mod, r % mod);
n /= mod;
r /= mod;
}
return result;
}
modint C(isize n, isize r) {
return combination(n, r);
}
};
} // namespace luz
#line 2 "src/math/modular-arithmetic/static-modint.hpp"
#line 4 "src/math/modular-arithmetic/static-modint.hpp"
#include <cassert>
#include <iostream>
namespace luz {
template < u32 mod >
class StaticPrimeModInt {
using modint = StaticPrimeModInt;
u32 v;
public:
StaticPrimeModInt(): v(0) {}
template < typename T >
StaticPrimeModInt(T v_) {
i64 x = (i64)(v_ % (i64)mod);
if (x < 0) x += mod;
v = (u32)x;
}
u32 val() const {
return v;
}
modint &operator+=(const modint &rhs) {
v += rhs.v;
if (v >= mod) v -= mod;
return *this;
}
modint &operator-=(const modint &rhs) {
v += mod - rhs.v;
if (v >= mod) v -= mod;
return *this;
}
modint &operator*=(const modint &rhs) {
v = (u32)(u64(1) * v * rhs.v % mod);
return *this;
}
modint &operator/=(const modint &rhs) {
*this *= rhs.inverse();
return *this;
}
modint operator+() const {
return *this;
}
modint operator-() const {
return modint() - *this;
}
friend modint operator+(const modint &lhs, const modint &rhs) {
return modint(lhs) += rhs;
}
friend modint operator-(const modint &lhs, const modint &rhs) {
return modint(lhs) -= rhs;
}
friend modint operator*(const modint &lhs, const modint &rhs) {
return modint(lhs) *= rhs;
}
friend modint operator/(const modint &lhs, const modint &rhs) {
return modint(lhs) /= rhs;
}
friend bool operator==(const modint &lhs, const modint &rhs) {
return lhs.v == rhs.v;
}
friend bool operator!=(const modint &lhs, const modint &rhs) {
return lhs.v != rhs.v;
}
modint pow(i64 n) const {
assert(0 <= n);
modint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
modint inverse() const {
assert(v != 0);
return pow(mod - 2);
}
static constexpr u32 get_mod() {
return mod;
}
friend std::ostream &operator<<(std::ostream &os,
const modint &m) {
os << m.val();
return os;
}
};
using modint998244353 = StaticPrimeModInt< 998244353 >;
using modint1000000007 = StaticPrimeModInt< 1000000007 >;
} // namespace luz
#line 6 "test/atcoder/arc117_c.test.cpp"
#line 8 "test/atcoder/arc117_c.test.cpp"
#include <string>
namespace luz {
void main_() {
using mint = StaticPrimeModInt< 3 >;
SmallModCombination< mint > mc;
usize n;
std::cin >> n;
std::string s;
std::cin >> s;
auto convert = [](char c) {
switch (c) {
case 'B':
return 0;
case 'W':
return 1;
case 'R':
return 2;
default:
exit(-1);
}
};
mint sum;
for (usize i = 0; i < n; i++) {
sum +=
(n & 1 ? 1 : -1) * convert(s[i]) * mc.combination(n - 1, i);
}
auto inverse = [](mint x) {
switch (x.val()) {
case 0:
return 'B';
case 1:
return 'W';
case 2:
return 'R';
default:
exit(-1);
}
};
std::cout << inverse(sum) << std::endl;
}
} // namespace luz
int main() {
luz::main_();
}