This documentation is automatically generated by online-judge-tools/verification-helper
#include "Math/BinomMod_ll.hpp"
#ifndef binom_mod_ll_HPP
#define binom_mod_ll_HPP
#include <vector>
#include <cassert>
#include "../Others/macros.hpp"
#include "extended_gcd.hpp"
struct BinomModLL {
private:
int MAX_N;
ll MOD;
std::vector<ll> factorial, factorial_inv;
/**
* @brief a の mod m における逆元 x を求める
* a*x == 1 を満たす x を求めたいということは、a*x + b*y == 1 を満たす x を求めたいということ
*/
ll mod_inverse(ll a, ll m) {
ll x, y;
ll g = extended_gcd(a, m, x, y);
assert(g == 1);
return (x % m + m) % m;
}
public:
BinomModLL(int MAX_N = 10000000, ll MOD = 998244353) : MAX_N(MAX_N), MOD(MOD) {
factorial[0] = 1;
for (int i = 1; i <= MAX_N; i++) {
factorial[i] = factorial[i - 1] * i % MOD;
}
factorial_inv[MAX_N] = mod_inverse(factorial[MAX_N], MOD);
for (int i = MAX_N - 1; i >= 0; i--) {
/*
((i+1)!)^(-1) ≡ (i+1)^(-1) * (i!)^(-1)
より、
(i!)^(-1) == ((i+1)!)^(-1) * (i+1)
*/
factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % MOD;
}
}
ll val(int N, int K) {
if (N < K || N < 0 || K < 0) {
return 0;
}
return factorial[N] * (factorial_inv[K] * factorial_inv[N - K] % MOD) % MOD;
}
};
#endif //binom_mod_ll_HPP
#line 1 "Math/BinomMod_ll.hpp"
#include <vector>
#include <cassert>
#line 1 "Others/macros.hpp"
#line 5 "Others/macros.hpp"
#include <queue>
#include <cmath>
using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define REF const auto&
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define BIT(i) (1LL << (i))
#define tbit(n, k) ((n >> k) & 1) // nの(上から)kビット目
#define bit(n, k) (n & (1LL << (k))) // nの(下から)kビット目
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define einr(l, x, r) (l <= x && x <= r)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define repl(i, a, b) for(long long i = (a); i < (b); i++)
#define erepl(i, a, b) for(long long i = (a); i <= (b); i++)
#define rrepl(i, a, b) for(long long i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR_subset(sub, bit) for (ll sub = (bit); sub >= 0; sub = (sub == 0 ? -1 : (sub - 1) & (bit)))
#define UNIQUE(v) (std::sort(all(v)), (v).erase(std::unique(all(v)), (v).end()))
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define VC(name, type, ...) vector<type> name(__VA_ARGS__)
#define VVC(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define VVVC(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define VVVVC(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define VVVVVC(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using maxpq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
if (a < b) { a = b; return 1; }
return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
if (a > b) { a = b; return 1; }
return 0;
}
const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
bool out_of_grid(const int& i, const int& j, const int& h, const int& w){
if(i < 0 || j < 0 || i >= h || j >= w) return true;
return false;
}
#line 1 "Math/extended_gcd.hpp"
/**
* @brief a * x + b * y == gcd(a, b)を満たす x, y を見つける
* @return gcd(a, b)
* x が a の逆元に相当
*/
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
/*
a * x0 + b * y0 == gcd(a, b)
↓ a = q * b + r(ユークリッドの互除法)
-> b * x1 + r * y1 == gcd(a, b)
-> ...
-> gcd(a, b) * xn + 0 * yn == gcd(a, b)
*/
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long prev_x, prev_y;
long long gcd = extended_gcd(b, a % b, prev_x, prev_y);
// 帰りがけに係数を更新
x = prev_y;
y = prev_x - (a / b) * prev_y;
return gcd;
}
#line 9 "Math/BinomMod_ll.hpp"
struct BinomModLL {
private:
int MAX_N;
ll MOD;
std::vector<ll> factorial, factorial_inv;
/**
* @brief a の mod m における逆元 x を求める
* a*x == 1 を満たす x を求めたいということは、a*x + b*y == 1 を満たす x を求めたいということ
*/
ll mod_inverse(ll a, ll m) {
ll x, y;
ll g = extended_gcd(a, m, x, y);
assert(g == 1);
return (x % m + m) % m;
}
public:
BinomModLL(int MAX_N = 10000000, ll MOD = 998244353) : MAX_N(MAX_N), MOD(MOD) {
factorial[0] = 1;
for (int i = 1; i <= MAX_N; i++) {
factorial[i] = factorial[i - 1] * i % MOD;
}
factorial_inv[MAX_N] = mod_inverse(factorial[MAX_N], MOD);
for (int i = MAX_N - 1; i >= 0; i--) {
/*
((i+1)!)^(-1) ≡ (i+1)^(-1) * (i!)^(-1)
より、
(i!)^(-1) == ((i+1)!)^(-1) * (i+1)
*/
factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % MOD;
}
}
ll val(int N, int K) {
if (N < K || N < 0 || K < 0) {
return 0;
}
return factorial[N] * (factorial_inv[K] * factorial_inv[N - K] % MOD) % MOD;
}
};