This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/combination.hpp"
#pragma once
#include "template.hpp"
// T modint
template<class T>
struct Combination {
vector<T> fact, inv_fact;
Combination(ll n) : fact(n+1), inv_fact(n+1) {
fact[0] = T(1);
for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * static_cast<T>(i);
inv_fact[n] = fact[n].inv();
for (ll i = n; i > 0; i--) inv_fact[i-1] = inv_fact[i] * static_cast<T>(i);
}
T P(ll n, ll k) const {
if (n < k or k < 0) return T(0);
return fact[n] * inv_fact[n-k];
}
T C(ll n, ll k) const {
if (n < k or k < 0) return T(0);
return fact[n] * inv_fact[n-k] * inv_fact[k];
}
T H(ll n, ll k) const {
if (n < 0 or k < 0) return T(0);
if (n == 0 and k == 0) return T(1);
return C(n+k-1, n-1);
}
};
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)n; i++)
#define rep3(i, l, r) for(ll i = l; i < (ll)r; i++)
#define per(i, n) for(ll i = (ll)n-1; i >= 0; i--)
#define per3(i, l, r) for(ll i = (ll)r-1; i >= (ll)l; i--)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
template<class T, class U> inline void cmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> inline void cmin(T &a, U b) { if (a > b) a = b; }
constexpr char el = '\n';
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) os << v[i] << (i+1 != (ll)v.size() ? " " : ""); return os; }
template<class T> istream &operator>>(istream &is, vector<T> &v) { for(T &i : v) is >> i; return is; }
struct IoSetup {
IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); }
} io_setup;
#line 3 "src/combination.hpp"
// T modint
template<class T>
struct Combination {
vector<T> fact, inv_fact;
Combination(ll n) : fact(n+1), inv_fact(n+1) {
fact[0] = T(1);
for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * static_cast<T>(i);
inv_fact[n] = fact[n].inv();
for (ll i = n; i > 0; i--) inv_fact[i-1] = inv_fact[i] * static_cast<T>(i);
}
T P(ll n, ll k) const {
if (n < k or k < 0) return T(0);
return fact[n] * inv_fact[n-k];
}
T C(ll n, ll k) const {
if (n < k or k < 0) return T(0);
return fact[n] * inv_fact[n-k] * inv_fact[k];
}
T H(ll n, ll k) const {
if (n < 0 or k < 0) return T(0);
if (n == 0 and k == 0) return T(1);
return C(n+k-1, n-1);
}
};