#line 1 "117.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A" #line 2 "/home/zawatin/compro/cp-documentation/Src/Template/IOSetting.hpp" #line 2 "/home/zawatin/compro/cp-documentation/Src/Template/TypeAlias.hpp" #include #include namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa #line 4 "/home/zawatin/compro/cp-documentation/Src/Template/IOSetting.hpp" #include #include namespace zawa { void SetFastIO() { std::cin.tie(nullptr)->sync_with_stdio(false); } void SetPrecision(u32 dig) { std::cout << std::fixed << std::setprecision(dig); } } // namespace zawa #line 2 "/home/zawatin/compro/cp-documentation/Src/Number/BinomalCoefficients.hpp" #line 4 "/home/zawatin/compro/cp-documentation/Src/Number/BinomalCoefficients.hpp" #include #include #include namespace zawa { template class BinomalCoefficients { public: static constexpr u64 MOD{T::mod()}; private: usize n_{}; std::vector F_{}, inv_{}, invF_{}; constexpr bool need(usize n) const noexcept { return n_ <= n; } void expand(usize n) { F_.reserve(n + 1); inv_.reserve(n + 1); invF_.reserve(n + 1); for (usize i{n_} ; i <= n ; i++) { F_.emplace_back(F_.back() * T{i}); inv_.emplace_back(MOD - inv_[MOD % i] * (MOD / i)); invF_.emplace_back(invF_.back() * inv_.back()); } n_ = n + 1; } public: constexpr usize size() const noexcept { return n_; } BinomalCoefficients() = default; BinomalCoefficients(usize n) : n_{2u}, F_{T{1}, T{1}}, inv_{T{0}, T{1}}, invF_{T{1}, T{1}} { assert(n); if (need(n)) expand(n); } T F(i32 n) { if (need(std::abs(n))) expand(static_cast(std::abs(n))); return (n >= 0 ? F_[n] : invF_[-n]); } T P(i32 p, i32 q) { if (q > p) return T{}; return F(p) * F(q - p); } T C(i32 p, i32 q) { if (q > p) return T{}; return P(p, q) * F(-q); } T H(i32 p, i32 q) { if (p == 0 and q == 0) return T{1}; return C(p + q - 1, q); } T B(const std::vector& b) { T res{1}; i32 sum{}; for (i32 x : b) { res *= F(-x); sum += x; } res *= F(sum); return res; } }; } // namespace zawa #line 5 "117.cpp" #line 7 "117.cpp" #include #include using mint = atcoder::modint1000000007; using namespace zawa; std::tuple parse() { std::string s; std::cin >> s; char c{s[0]}; int i{2}; int p{}; for (; s[i] != ',' ; i++) { p = (p * 10) + (s[i] - '0'); } int q{}; for (i++ ; s[i] != ')' ; i++) { q = (q * 10) + (s[i] - '0'); } return { c, p, q }; } void solve() { int t; std::cin >> t; BinomalCoefficients comb(1000000); for (int _{} ; _ < t ; _++) { auto [c, p, q]{parse()}; if (c == 'C') std::cout << comb.C(p, q).val() << '\n'; else if (c == 'P') std::cout << comb.P(p, q).val() << '\n'; else std::cout << comb.H(p, q).val() << '\n'; } } int main() { #ifdef ONLINE_JUDGE solve(); #else std::cout << "Hello World" << '\n'; #endif }