#pragma once
#include <vector>
#include <algorithm>
#include <assert.h>
typedef long long ll;
struct Factorial
{
	Factorial(int n_) :n(n_) { init(); }
	const ll mod = 1000000007;//modは素数だと仮定

	int n;
	std::vector<ll> fac_, inv_;


	void init() {
		fac_.resize(n+1);
		inv_.resize(n+1);
		calc_factorial();
		calc_inv();
	}

	//累乗の計算
	void calc_factorial() {
		fac_[0] = 1;
		for (int i = 1; i <= n; i++) {
			fac_[i] = i * fac_[i - 1] % mod;
		}
	}
	
	ll mod_pow(ll x, ll n, ll mod) {
		if (n == 0) { return 1; }
		ll res = mod_pow(x * x % mod, n / 2, mod);
		if (n & 1) { res = res * x % mod; }
		return res;
	}
	//逆元の計算
	void calc_inv() {
		inv_[n] = mod_pow(fac_[n], mod - 2, mod);
		for (int i = n - 1; i >= 0; i--) {
			inv_[i] = (i + 1) * inv_[i + 1] % mod;
		}
	}

	//逆元を返す
	ll inv(size_t i) {
		assert(i >= 0 && i <= n);
		return inv_[i];
	}
	//1  以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選ぶパターンの数
	ll comb(int n, int k) {
		if (n < k)return 0;
		ll res = fac_[n];
		res = res * inv_[n - k] % mod;
		res = res * inv_[k] % mod;
		return res;
	}

	//1  以上 N 以下の N 個の整数の中から，相異なる K 個の整数を選び，順番に並べるパターンの数を P(N,K)
	ll perm(int n, int k) {
		if (n < k)return 0;
		ll res = fac_[n];
		res = res * inv_[n - k] % mod;
		return res;
	}
	//1 以上 N 以下の N 個の整数の中から，重複を許して K 個の整数を選ぶパターンの数
	ll h(int n, int k) {
		if (n == 0 && k == 0)return 1;
		return comb(n + k - 1, k);
	}
	//階乗(n!)を返す
	ll fac(size_t i) {
		assert(i >= 0 && i <= n);
		return fac_[i];
	}
};