結果
| 問題 | No.117 組み合わせの数 |
| コンテスト | |
| ユーザー |
 T101010101
|
| 提出日時 | 2025-12-01 12:14:25 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 152 ms / 5,000 ms |
| コード長 | 30,995 bytes |
| コンパイル時間 | 5,239 ms |
| コンパイル使用メモリ | 377,700 KB |
| 実行使用メモリ | 50,084 KB |
| 最終ジャッジ日時 | 2025-12-01 12:14:32 |
| 合計ジャッジ時間 | 6,657 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 |
ソースコード
/* #region */
#ifdef ONLINE_JUDGE
#define NDEBUG
#pragma GCC optimize("O3,unroll-loops")
#ifdef ATCODER
#pragma GCC target("sse,sse2,sse3,ssse3,fma,abm,mmx,bmi,bmi2,popcnt,lzcnt")
#pragma GCC target("avx2") // NG : CF, CodeChef, HamakoOJ
#include <boost/unordered/unordered_flat_map.hpp>
#include <boost/unordered/unordered_flat_set.hpp>
#define unordered_map boost::unordered_flat_map
#define unordered_set boost::unordered_flat_set
#endif
#endif
#include <bits/extc++.h>
// #include <atcoder/all>
// using namespace atcoder;
using namespace std;
using namespace __gnu_pbds;
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using lll = mp::cpp_int;
// using lld = mp::cpp_dec_float_50; // 十進50桁. ldは19桁.
// // using lld = mp::cpp_dec_float_100;
// // using lld = mp::number<mp::cpp_dec_float<200>>;
// lld Beps = 0.00000000000000000000000000000001; // 1e-32
// const bool equals(lld a, lld b) { return mp::fabs(a - b) < Beps; }
#define int ll
#define endl '\n'
using ll = long long;
using ld = long double;
constexpr ld PI = acosl(-1);
constexpr ld EPS = 1e-10;
constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 61;
// constexpr int MOD = 998244353;
constexpr int MOD = 1000000007;
constexpr array<int, 9> dx = {0, 1, 0, -1, 1, 1, -1, -1, 0}; // → ↓ ← ↑ ↘ ↙ ↖ ↗ 自
constexpr array<int, 9> dy = {1, 0, -1, 0, 1, -1, -1, 1, 0};
inline namespace util {
constexpr bool equals(ld a, ld b) { return fabs((a) - (b)) < EPS; }
template <typename T> constexpr bool overflow_if_add(T a, T b) {
assert(a >= 0 && b >= 0);
return (numeric_limits<T>::max() - a) < b;
}
template <typename T> constexpr bool overflow_if_mul(T a, T b) { // 整数型以外は未verify
assert(a >= 0 && b >= 0);
return (numeric_limits<T>::max() / a) < b;
}
template <typename T> constexpr bool overflow_if_shift(T a, int k) {
assert(a >= 0);
if (a == 0) return false;
if (k > 64 or k < 0) return true;
if (((__int128_t)a << k) > numeric_limits<T>::max()) return true;
return false;
}
constexpr __int128_t POW(__int128_t x, int n) {
assert(n >= 0);
__int128_t ret = 1;
while (n > 0) {
if (n & 1) ret *= x;
if (n == 1) break;
assert(!overflow_if_mul(x, x));
x *= x;
n >>= 1;
}
return ret;
}
constexpr int64_t pow64(int64_t x, int n) {
assert(n >= 0);
int64_t ret = 1;
while (n > 0) {
if (n & 1) ret *= x;
if (n == 1) break;
assert(!overflow_if_mul(x, x));
x *= x;
n >>= 1;
}
return ret;
}
constexpr int per(int x, int y) { // x = qy + r (0 <= r < y) を満たすq
assert(y != 0);
if (x >= 0 && y > 0) return x / y;
if (x >= 0 && y < 0) return x / y;
if (x < 0 && y < 0) return x / y + (x % y < 0);
return x / y - (x % y < 0); // (x < 0 && y > 0)
}
constexpr int mod(int x, int y) { // x = qy + r (0 <= r < y) を満たすr
assert(y != 0);
return x - y * per(x, y);
} // https://yukicoder.me/problems/no/2781
constexpr int floor(int x, int y) { // (ld)x / y 以下の最大の整数
assert(y != 0);
if (y < 0) x = -x, y = -y;
return x >= 0 ? x / y : (x + 1) / y - 1;
}
constexpr int ceil(int x, int y) { // (ld)x / y 以上の最小の整数
assert(y != 0);
if (y < 0) x = -x, y = -y;
return x > 0 ? (x - 1) / y + 1 : x / y;
}
constexpr int round(int x, int y) { // (ld)x / y を小数第1位について四捨五入
assert(y != 0);
if (x*y < 0) return -((abs(x) * 2 + abs(y)) / (abs(y) * 2)); // https://www.acmicpc.net/problem/2108
return (x * 2 + y) / (y * 2);
}
constexpr int round(int x, int y, int k) { // (ld)x / y を10^kの位に関して四捨五入
assert(y != 0 && k >= 0);
if (k == 0) return (x * 2 + y) / (y * 2);
x /= y * POW(10, k - 1);
if (x % 10 >= 5) return (x + 10 - x % 10) * POW(10, k - 1);
return x * POW(10, k - 1);
}
constexpr int round2(int x, int y) { // 五捨五超入 // 未verify
assert(y != 0);
if (y < 0) y = -y, x = -x;
int z = x / y;
if ((z * 2 + 1) * y <= y * 2) z++;
return z;
}
constexpr int floor(ld x) { // 未. 負数でも小さい方に丸める
if (x > -EPS) return (int)(floorl(x + EPS) + EPS);
return -(int)((ceill(-x - EPS)) + EPS);
}
constexpr int ceil(ld x) { // 未. 負数でも大きい方に丸める
if (x > EPS) return (int)(ceill(x - EPS) + EPS);
return -(int)((floorl(-x + EPS)) + EPS);
}
constexpr int round(ld x) { // 未. 負数でも.5の場合は大きい方に丸める
if (x > EPS) return (int)(roundl(x + EPS) + EPS);
return (int)(roundl(x + EPS) - EPS);
}
// constexpr int get(ld x, int k) { // 未. xの10^kの位の桁
// }
constexpr ld floor(ld x, int k) { // xを10^kの位に関してflooring
ld d = pow(10, -k);
return floor(x * d) / d; // 未verify
}
constexpr ld ceil(ld x, int k) { // xを10^kの位に関してceiling
ld d = pow(10, -k);
return ceil(x * d) / d; // 未verify
}
constexpr ld round(ld x, int k) { // xを10^kの位に関して四捨五入.
ld d = pow(10, -k);
return round(x * d) / d;
}
// constexpr int kth(int x, int y, int k) { // x / yの10^kの位の桁
// }
constexpr int floor(ld x, ld y) { // 誤差対策TODO
assert(!equals(y, 0));
return floorl(x / y);
// floor(x) = ceil(x - 1) という話も
}
constexpr int ceil(ld x, ld y) { // 誤差対策TODO // ceil(p/q) = -floor(-(p/q))らしい
assert(!equals(y, 0));
return ceill(x / y);
// ceil(x) = floor(x + 1)
}
constexpr int perl(ld x, ld y) { // x = qy + r (0 <= r < y, qは整数) を満たす q
// 未verify. 誤差対策TODO. EPS外してもいいかも。
assert(!equals(y, 0));
if (x >= 0 && y > 0) return floorl(x / y) + EPS;
if (x >= 0 && y < 0) return -floorl(x / fabs(y));
if (x < 0 && y < 0) return floorl(x / y) + (x - floorl(x/y)*y < -EPS);
return floorl(x / y) - (x - floorl(x/y)*y < -EPS); // (x < 0 && y > 0)
}
constexpr ld modl(ld x, ld y) { // x = qy + r (0 <= r < y, qは整数) を満たす r
// 未verify. 誤差対策TODO. -0.0が返りうる。
assert(!equals(y, 0));
if (x >= 0) return x - fabs(y)*fabs(perl(x, y));
return x - fabs(y)*floor(x, fabs(y));
}
constexpr int seisuu(ld x) { return (int)x; } // 整数部分. 誤差対策TODO
constexpr int modf(ld x) {
if (x < 0) return ceil(x);
else return floor(x);
}
// 正なら+EPS, 負なら-EPSしてから、文字列に直して小数点以下を捨てる?
constexpr int seisuu(int x, int y) {
assert(y != 0);
return x / y;
}
constexpr int seisuu(ld x, ld y) { // 誤差対策TODO
assert(!equals(y, 0));
return (int)(x / y);
}
constexpr int floor_log(int base, int x) { // log_base{x} のfloor
assert(base >= 2);
int ret = 0, now = 1;
while (now <= x) {
now *= base;
if (now <= x) ret++;
}
return ret;
}
constexpr int ceil_log(int base, int x) { // log_base{x} のceil
assert(base >= 2);
int ret = 0, now = 1;
while (now < x) {
now *= base;
ret++;
}
return ret;
}
template <typename T> constexpr pair<T, T> max(const pair<T, T> &a, const pair<T, T> &b) {
if (a.first > b.first or a.first == b.first && a.second > b.second) return a;
return b;
}
template <typename T> constexpr pair<T, T> min(const pair<T, T> &a, const pair<T, T> &b) {
if (a.first < b.first or a.first == b.first && a.second < b.second) return a;
return b;
}
template <typename T> constexpr bool chmax(T &a, const T &b) {
if (a < b) { a = b; return true; } return false;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
if (a > b) { a = b; return true; } return false;
}
template <typename T> constexpr bool chmax(pair<T, T> &a, const pair<T, T> &b) {
if (a.first < b.first or a.first == b.first && a.second < b.second) { a = b; return true; }
return false;
}
template <typename T> constexpr bool chmin(pair<T, T> &a, const pair<T, T> &b) {
if (a.first > b.first or a.first == b.first && a.second > b.second) { a = b; return true; }
return false;
}
template <typename T> constexpr T mid(T a, T b, T c) {
return max(min(a, b), min(max(a, b), c));
}
template <typename T, typename... Args>
constexpr void Sort(T& a, T& b, Args&... args) noexcept {
vector<T> vec = {a, b, args...};
sort(vec.begin(), vec.end());
auto it = vec.begin();
a = *it++; b = *it++;
int dummy[] = {0, (args = *it++, 0)...};
static_cast<void>(dummy);
}
template <typename T, typename... Args>
constexpr void Sortr(T& a, T& b, Args&... args) noexcept {
vector<T> vec = {a, b, args...};
sort(vec.rbegin(), vec.rend());
auto it = vec.begin();
a = *it++; b = *it++;
int dummy[] = {0, (args = *it++, 0)...};
static_cast<void>(dummy);
}
template <typename T>
constexpr void sort(vector<T> &A, vector<T> &B) noexcept { // Aをキーにして {A[i], B[i]} をソート
vector<pair<T, T>> P(A.size());
for (int i = 0; i < (int)A.size(); i++) P[i] = {A[i], B[i]};
sort(P.begin(), P.end());
for (int i = 0; i < (int)A.size(); i++) A[i] = P[i].first, B[i] = P[i].second;
}
istream &operator >>(istream &is, __int128_t& x) {
string S; is >> S;
__int128_t ret = 0;
bool neg = false;
if (S[0] == '-') neg = true;
for (int i = neg; i < (int)S.size(); i++) {
ret = ret * 10 + S[i] - '0';
}
x = neg ? -ret : ret;
return is;
}
ostream &operator <<(ostream &os, __int128_t x) {
ostream::sentry s(os);
if (s) {
__uint128_t tmp = x < 0 ? -x : x;
char buffer[128]; char *d = end(buffer);
do {
--d; *d = "0123456789"[tmp % 10]; tmp /= 10;
} while (tmp != 0);
if (x < 0) { --d; *d = '-'; }
int len = end(buffer) - d;
if (os.rdbuf()->sputn(d, len) != len) os.setstate(ios_base::badbit);
}
return os;
}
__int128_t abs(__int128_t x) {
return x < 0 ? -x : x;
}
__int128_t sto128(const string &S) {
assert(!S.empty());
__int128_t ret = 0;
bool neg = false;
if (S[0] == '-') neg = true;
for (int i = neg; i < (int)S.size(); i++) {
ret = ret * 10 + S[i] - '0';
}
return neg ? -ret : ret;
}
__int128_t gcd(__int128_t a, __int128_t b) {
// a = abs(a); b = abs(b);
return b ? gcd(b, a % b) : a;
}
__int128_t lcm(__int128_t a, __int128_t b) {
if (a == 0 or b == 0) return 0;
// a = abs(a); b = abs(b);
return a / gcd(a, b) * b;
// lcmが__int128_tに収まる必要あり
}
string to_string(double x, int k) { // 小数第k+1を四捨五入して小数第k位までを出力
// 切り捨てがほしい場合は to_string(x, k+1) として pop_back() すればよい?
assert(k >= 0);
ostringstream os;
os << fixed << setprecision(k) << x;
return os.str();
}
string to_string(__int128_t x) {
if (x == 0) return "0";
string ret = "";
bool neg = false;
if (x < 0) { neg = true; x = -x; }
while (x) { ret += (char)('0' + x % 10); x /= 10; }
if (neg) ret += '-';
reverse(ret.begin(), ret.end());
return ret;
}
string to_string(char c) { return string(1, c); }
}
inline namespace bit_function {
using i64 = int64_t; constexpr int _mx = 62;
// using i64 = uint64_t; constexpr int _mx = 63; // 1LLを1uLLに直す
// 区間は [l, r)
constexpr i64 lrmask(int l, int r) { assert(r < _mx); return (1LL << r) - (1LL << l); }
constexpr i64 sub_bit(i64 x, int l, int r) { assert(r < _mx); return (x & ((1LL << r) - (1LL << l))) >> l; } // r溢れ可
constexpr i64 bit_width(i64 x) { return (x == 0) ? 1 : 64 - __builtin_clzll(x); }
constexpr i64 popcount(i64 x) { return __builtin_popcountll(x); }
constexpr i64 popcount(i64 x, int l, int r) { return popcount(sub_bit(x, l, r)); }
constexpr i64 unpopcount(i64 x) { return bit_width(x) - popcount(x); } // 最上位bitより下のみ
constexpr i64 unpopcount(i64 x, int l, int r) { return r - l - popcount(sub_bit(x, l, r)); } // 最上位bitより上も含まれうる
constexpr bool is_pow2(i64 x) { return popcount(x) == 1; }
constexpr bool is_pow4(i64 x) { return popcount(x) == 1 && __builtin_ctzll(x) % 2 == 0; }
constexpr int top_bit(i64 x) { return (x == 0) ? -1 : 63 - __builtin_clzll(x); }
constexpr int bot_bit(i64 x) { return (x == 0) ? -1 : __builtin_ctzll(x); }
constexpr i64 msb(i64 x) { return (x == 0) ? 0 : 1LL << (63 - __builtin_clzll(x)); } // mask
constexpr i64 lsb(i64 x) { return (x & -x); } // mask
constexpr int next_bit(i64 x, int k) {
assert(k < _mx - 1);
i64 mask = x & ~((1LL << (k + 1)) - 1); // k+1桁目以上のビットのみ残す
return (mask == 0) ? -1 : __builtin_ctzll(mask);
}
constexpr int prev_bit(i64 x, int k) {
assert(k < _mx);
i64 mask = x & ((1LL << k) - 1); // k桁目未満のビットのみ残す
return (mask == 0) ? -1 : 63 - __builtin_clzll(mask);
}
constexpr int kth_bit(i64 x, int k) { // 下からk番目の1の位置。kは1-indexed, 位置は0-indexed
if (popcount(x) < k) return -1;
int pos = 0, cnt = 0;
while (x > 0) {
if ((x & 1) && (++cnt == k)) return pos;
x >>= 1; pos++;
}
}
constexpr int countl_zero(i64 x) { return (x == 0) ? 64 : __builtin_clzll(x); }
constexpr int countr_zero(i64 x) { return (x == 0) ? 64 : __builtin_ctzll(x); }
constexpr int countl_one(i64 x) { // std::countl_oneと定義が異なるので注意
if (x == 0) return 0;
i64 ret = 0, k = 63 - __builtin_clzll(x);
while (k != -1 && (x & (1LL << k))) { k--; ret++; }
return ret;
}
constexpr int countr_one(i64 x) { return (x == 0) ? 0 : popcount(x ^ (x & -~x)); }
constexpr i64 l_one_mask(i64 x) { // 最上位で連なってる1のmask
int cnt = countl_one(x);
return (cnt == 0) ? 0 : (x & (~((1LL << (bit_width(x) - cnt)) - 1)));
}
constexpr i64 r_one_mask(i64 x) { // 最下位で連なってる1のmask
int cnt = countr_one(x);
return (cnt == 0) ? 0 : (x & ((1LL << cnt) - 1));
}
constexpr int floor_log2(i64 x) { assert(x > 0); return 63 - __builtin_clzll(x); } // top_bit
constexpr int ceil_log2(i64 x) { assert(x > 0); return 64 - __builtin_clzll(x - 1); }
constexpr i64 bit_floor(i64 x) { if (x == 0) return 0; return 1LL << (63 - __builtin_clzll(x)); } // msb
constexpr i64 bit_ceil(i64 x) { if (x == 0) return 0; return 1LL << (64 - __builtin_clzll(x - 1)); }
constexpr i64 rotl(i64 x, int k) { // 有効bit内でrotate. オーバーフロー注意
i64 w = bit_width(x); k = mod(k, w);
assert(!overflow_if_shift(x, k));
return ((x << k) | (x >> (w - k))) & ((1LL << w) - 1);
}
constexpr i64 rotr(i64 x, int k) {
i64 w = bit_width(x); k = mod(k, w);
assert(!overflow_if_shift(x, w - k));
return ((x >> k) | (x << (w - k))) & ((1LL << w) - 1);
}
constexpr i64 bit_reverse(i64 x) { // 有効bit内で左右反転
i64 r = 0, w = bit_width(x);
for (i64 i = 0; i < w; i++) r |= ((x >> i) & 1) << (w - i - 1);
return r;
}
constexpr bool is_palindrome(i64 x) { return x == bit_reverse(x); }
constexpr bool is_palindrome(i64 x, int l, int r) { i64 b = sub_bit(x, l, r); return b == bit_reverse(b); }
constexpr i64 concat(i64 a, i64 b) { return (a << bit_width(b)) | b; } // オーバーフロー注意
constexpr i64 erase(i64 x, int l, int r) { return (x >> r << l) | (x & ((1LL << l) - 1)); } // [l, r) をカット
constexpr i64 hamming(i64 a, i64 b) { return popcount(a ^ b); }
constexpr i64 hamming(i64 a, i64 b, int l, int r) { return popcount(sub_bit(a, l, r) ^ sub_bit(b, l, r)); }
constexpr i64 compcount(i64 x) { return (popcount(x ^ (x >> 1)) + (x & 1)) / 2; }
constexpr i64 compcount2(i64 x) { return compcount(x & (x >> 1)); } // 長さ2以上の連結成分の個数
constexpr i64 adjacount(i64 x) { return popcount(x & (x >> 1)); } // 隣接する1のペアの個数
constexpr i64 next_combination(i64 x) {
assert(x != 0);
i64 t = x | (x - 1); return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctzll(x) + 1));
}
vector<int> popvec(i64 x) {
vector<int> ret;
i64 b = 1;
for (int k = 0; x >= b; k++, b <<= 1) {
if (x & b) ret.push_back(k);
}
return ret;
}
}
template<typename T>
struct Edge {
int from, to;
T cost;
Edge() {}
Edge(int to, T cost) : from(-1), to(to), cost(cost) {}
Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
bool operator ==(const Edge &e) const {
return this->from == e.from && this->to == e.to && this->cost == e.cost;
}
bool operator !=(const Edge &e) const {
return this->from != e.from or this->to != e.to or this->cost != e.cost;
}
bool operator <(const Edge &e) const { return this->cost < e.cost; }
bool operator >(const Edge &e) const { return this->cost > e.cost; }
};
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
class RNG {
using state_type = uint32_t; // 負数非対応
using result_type = uint32_t;
public:
RNG() {
auto now = chrono::high_resolution_clock::now();
w = static_cast<state_type>(now.time_since_epoch().count() & 0xFFFFFFFF);
}
// RNG(state_type seed = 88675123) : w(seed) {}
constexpr result_type Int(state_type r) { // [0, r]
return _Int(r + 1);
}
constexpr result_type Int(state_type l, state_type r) { // [l, r]
return _Int(r - l + 1) + l;
}
constexpr double prob() { // [0, 1]
return (*this)() * INV_MAX;
}
constexpr double Double(double l, double r) { // [l, r]
return prob() * (r - l) + l;
}
vector<result_type> Seq(int N, state_type l, state_type r) { // [l, r]
vector<result_type> ret(N);
for (int i = 0; i < N; i++) ret[i] = _Int(r - l + 1) + l;
return ret;
}
vector<result_type> Perm(int N) {
vector<result_type> ret(N);
iota(ret.begin(), ret.end(), 0);
for (int i = 0; i < N; i++) {
int j = _Int(N - i) + i;
swap(ret[i], ret[j]);
}
return ret;
}
string Str(int N, bool small = true) {
string ret(N, ' ');
for (int i = 0; i < N; i++) {
if (small) ret[i] = (char)Int('a', 'z');
else ret[i] = (char)Int('A', 'Z');
}
return ret;
}
private:
state_type x = 123456789, y = 362436039, z = 521288629, w = 88675123;
constexpr static double INV_MAX = 1.0 / 0xFFFFFFFF;
constexpr result_type operator()() {
state_type t = x ^ (x << 11);
x = y, y = z, z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
constexpr result_type _Int(state_type r) { // [0, r)
return ((uint64_t) (*this)() * r) >> 32;
}
} rnd;
template<typename T>
class Compress {
public:
Compress() = default;
template<typename... Vecs>
Compress(const Vecs&... vecs) {
(uniqV.insert(uniqV.end(), vecs.begin(), vecs.end()), ...);
sort(uniqV.begin(), uniqV.end());
uniqV.erase(unique(uniqV.begin(), uniqV.end()), uniqV.end());
sz = uniqV.size();
}
int size() const noexcept { return sz; }
vector<int> zip(const vector<T> &V) const {
vector<int> ret(V.size());
for (int i = 0; i < (int)V.size(); i++) {
ret[i] = encode(V[i]);
}
return ret;
}
vector<T> unzip(const vector<int> &V) const {
vector<T> ret(V.size());
for (int i = 0; i < (int)V.size(); i++) {
ret[i] = decode(V[i]);
}
return ret;
}
int encode(T x) const { // xが存在しない場合は挿入すべき位置を返す
auto it = lower_bound(uniqV.begin(), uniqV.end(), x);
return it - uniqV.begin();
}
T decode(int x) const {
assert(0 <= x && x < sz);
return uniqV[x];
}
private:
int sz = 0;
vector<T> uniqV;
};
class UnionFind {
public:
UnionFind() = default;
UnionFind(int N) : par(N), sz(N, 1) {
iota(par.begin(), par.end(), 0);
}
int root(int x) {
if (par[x] == x) return x;
return (par[x] = root(par[x]));
}
bool unite(int x, int y) {
int rx = root(x);
int ry = root(y);
if (rx == ry) return false;
if (sz[rx] < sz[ry]) swap(rx, ry);
sz[rx] += sz[ry];
par[ry] = rx;
return true;
}
bool issame(int x, int y) { return (root(x) == root(y)); }
int size(int x) { return sz[root(x)]; }
vector<vector<int>> groups() {
int N = par.size();
vector<vector<int>> G(N);
for (int x = 0; x < N; x++) {
G[root(x)].push_back(x);
}
G.erase( remove_if(G.begin(), G.end(),
[&](const vector<int>& V) { return V.empty(); }), G.end());
return G;
}
private:
vector<int> par, sz;
};
template<typename T>
class BIT {
public:
BIT(int N_, int x = 0) : N(N_ + 1) {
bit[0].assign(N, 0); bit[1].assign(N, 0);
if (x != 0) {
for (int i = 0; i < N; i++) add(i, x);
}
}
BIT(const vector<T> &A) : N(A.size() + 1) {
bit[0].assign(N, 0); bit[1].assign(N, 0);
for (int i = 0; i < (int)A.size(); i++) add(i, A[i]);
}
void add(int l, int r, T x) {
add_sub(0, l + 1, -x * l); add_sub(0, r + 1, x * r);
add_sub(1, l + 1, x); add_sub(1, r + 1, -x);
}
void add(int i, T x) { add(i, i + 1, x); }
T sum(int i) const { return sum_sub(0, i) + sum_sub(1, i) * i; }
T sum(int l, int r) const { return sum(r) - sum(l); }
T get(int i) const { return sum(i, i + 1); }
void set(int i, T x) { T s = get(i); add(i, -s + x); }
private:
int N;
vector<T> bit[2];
void add_sub(int p, int i, T x) {
while (i < N) { bit[p][i] += x; i += (i & -i); }
}
T sum_sub(int p, int i) const {
T ret = T(0);
while (i > 0) { ret += bit[p][i]; i -= (i & -i); }
return ret;
}
};
template<uint_fast64_t Modulus>
class Modint {
using u64 = std::uint_fast64_t;
using i64 = std::int_fast64_t;
public:
u64 val = 0;
static constexpr u64 mod = Modulus;
constexpr Modint() noexcept = default;
constexpr Modint(u64 x) noexcept : val(util::mod(x, mod)) {}
constexpr Modint(const Modint &r) noexcept = default;
constexpr Modint &operator =(const Modint &r) noexcept = default;
static constexpr Modint raw(u64 x) noexcept { Modint ret; ret.val = x; return ret; }
constexpr Modint operator +() const noexcept { return *this; } // 単項
constexpr Modint operator -() const noexcept { return raw(val ? mod - val : 0); }
constexpr Modint operator +(const Modint &r) const noexcept { return Modint(*this) += r; }
constexpr Modint operator +(int q) const noexcept { return Modint(*this) += Modint(q); }
constexpr Modint operator -(const Modint &r) const noexcept { return Modint(*this) -= r; }
constexpr Modint operator -(int q) const noexcept { return Modint(*this) -= Modint(q); }
constexpr Modint operator *(const Modint &r) const noexcept { return Modint(*this) *= r; }
constexpr Modint operator *(int q) const noexcept { return Modint(*this) *= Modint(q); }
constexpr Modint operator /(const Modint &r) const noexcept { return Modint(*this) /= r; }
constexpr Modint operator /(int q) const noexcept { return Modint(*this) /= Modint(q); }
constexpr Modint &operator ++() noexcept { if (++val >= mod) val -= mod; return *this; } // 前置
constexpr Modint operator ++(signed) noexcept { Modint tmp = *this; ++*this; return tmp; } // 後置
constexpr Modint &operator --() noexcept { if (val == 0) val = mod; val--; return *this; }
constexpr Modint operator --(signed) noexcept { Modint tmp = *this; --*this; return tmp; }
constexpr Modint &operator +=(const Modint &r) noexcept { if ((val += r.val) >= mod) val -= mod; return *this; }
constexpr Modint &operator +=(int q) noexcept { return *this += Modint(q); }
constexpr Modint &operator -=(const Modint &r) noexcept { if (val < r.val) val += mod; val -= r.val; return *this; }
constexpr Modint &operator -=(int q) noexcept { return *this -= Modint(q); }
constexpr Modint &operator *=(const Modint &r) noexcept { val = val * r.val % mod; return *this; }
constexpr Modint &operator *=(int q) noexcept { return *this *= Modint(q); }
constexpr Modint &operator /=(const Modint &r) noexcept {
i64 a = r.val, b = mod, u = 1, v = 0;
while (b) { i64 t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
val = val * util::mod(u, mod) % mod;
return *this;
}
constexpr Modint &operator /=(int q) noexcept { return *this /= Modint(q); }
constexpr bool operator ==(const Modint &r) const noexcept { return val == r.val; }
constexpr bool operator !=(const Modint &r) const noexcept { return val != r.val; }
constexpr bool operator <(const Modint &r) const noexcept { return val < r.val; }
constexpr bool operator >(const Modint &r) const noexcept { return val > r.val; }
constexpr bool operator <=(const Modint &r) const noexcept { return val <= r.val; }
constexpr bool operator >=(const Modint &r) const noexcept { return val >= r.val; }
constexpr Modint inv() const noexcept { return Modint(1) /= *this; }
constexpr Modint pow(int n) const noexcept {
Modint ret = 1, base = *this;
if (n < 0) { base = base.inv(); n = -n; }
while (n > 0) {
if (n & 1) ret *= base;
base *= base;
n >>= 1;
}
return ret;
}
friend istream &operator >>(istream &is, Modint &x) {
int t; is >> t; x = Modint(t); return is;
}
friend ostream &operator <<(ostream &os, const Modint &x) {
return os << x.val;
}
};
using mint = Modint<MOD>;
mint modpow(mint x, int n) {
if (n < 0) return (mint)1 / modpow(x, -n); // 未verify
mint ret = 1;
while (n > 0) {
if (n & 1) ret *= x;
x *= x;
n >>= 1;
}
return ret;
}
int modpow(__int128_t x, int n, int mod) {
if (n == 0 && mod == 1) return 0;
assert(n >= 0 && mod > 0); // TODO: n <= -1
__int128_t ret = 1;
x %= mod;
while (n > 0) {
if (n & 1) ret = ret * x % mod;
x = x * x % mod;
n /= 2;
}
return ret;
}
// int modinv(__int128_t x, int mod) { //
// assert(mod > 0);
// // assert(x > 0);
// if (x == 1 or x == 0) return 1;
// return mod - modinv(mod % x, mod) * (mod / x) % mod;
// }
inline namespace combination {
vector<mint> _fac, _finv, _inv;
int _com_size = 0;
void COMinit(int N) {
assert(N > 0);
_fac.resize(N + 1); _finv.resize(N + 1); _inv.resize(N + 1);
_fac[0] = _fac[1] = 1; _finv[0] = _finv[1] = 1; _inv[1] = 1;
for (int i = 2; i <= N; i++) {
_fac[i] = _fac[i-1] * mint(i);
_inv[i] = -_inv[MOD % i] * mint(MOD / i);
_finv[i] = _finv[i - 1] * _inv[i];
}
_com_size = N;
}
mint FAC(int N) {
assert(N <= _com_size);
if (N < 0) return 0;
return _fac[N];
}
mint FACinv(int N) {
assert(N <= _com_size);
if (N < 0) return 0;
return _finv[N];
}
mint COM(int N, int K) {
assert(N <= _com_size);
if (N < K) return 0;
if (N < 0 or K < 0) return 0;
return _fac[N] * _finv[K] * _finv[N - K];
}
mint COMinv(int N, int K) {
assert(N <= _com_size);
if (N < K) return 0;
if (N < 0 or K < 0) return 0;
return _finv[N] * _fac[K] * _fac[N - K];
}
mint MCOM(const vector<int> &V) {
assert(accumulate(V.begin(), V.end(), 0) <= _com_size);
int N = 0;
for (int i = 0; i < (int)V.size(); i++) N += V[i];
mint ret = _fac[N];
for (int i = 0; i < (int)V.size(); i++) ret *= _finv[V[i]];
return ret;
}
mint PERM(int N, int K) {
assert(N <= _com_size);
if (N < K) return 0;
if (N < 0 or K < 0) return 0;
return _fac[N] * _finv[N - K];
}
mint NHK(int N, int K) { // initのサイズに注意
assert(N <= _com_size);
// if (N < 0 or K < 0) return 0;
if (N == 0 && K == 0) return 1;
return COM(N + K - 1, K);
}
}
inline namespace timer {
chrono::system_clock::time_point _start;
void reset() {
_start = chrono::system_clock::now();
}
ll now() {
auto cur = chrono::system_clock::now();
return chrono::duration_cast<chrono::milliseconds>(cur - _start).count();
}
}
__attribute__((constructor))
void constructor() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
reset();
}
/* #endregion */
signed main() {
COMinit(2e6 + 1);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
char c, g;
int N, K;
cin >> c >> g >> N >> g >> K >> g;
if (c == 'C') {
cout << COM(N, K) << endl;
} else if (c == 'P') {
cout << PERM(N, K) << endl;
} else {
cout << NHK(N, K) << endl;
}
}
}