class Combinatorics { private: vector fact, inv_fact; int max_n; public: // 预处理阶乘和逆阶乘,O(n) Combinatorics(int n) : max_n(n) { fact.resize(n + 1); inv_fact.resize(n + 1); fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i % MOD; } inv_fact[n] = inv(fact[n]); for (int i = n - 1; i >= 0; i--) { inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD; } } // 快速幂计算逆元,O(log MOD) ll inv(ll x) { return qpow(x, MOD - 2); } // 快速幂,O(log exponent) ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } // 组合数C(n,k),O(1) ll C(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD; } // 排列数A(n,k),O(1) ll A(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * inv_fact[n - k] % MOD; } // 卢卡斯定理计算组合数,适用于n,k很大但MOD较小的情况 ll Lucas(ll n, ll k) { if (k == 0) return 1; return C(n % MOD, k % MOD) * Lucas(n / MOD, k / MOD) % MOD; } // 第二类斯特林数S(n,k),将n个元素划分为k个非空子集,O(nk) ll Stirling2(int n, int k) { ll res = 0; for (int i = 0; i <= k; i++) { ll term = C(k, i) * qpow(i, n) % MOD; if ((k - i) % 2) { res = (res - term + MOD) % MOD; } else { res = (res + term) % MOD; } } return res * inv_fact[k] % MOD; } // 贝尔数B(n),基于第二类斯特林数的实现,O(n^2) // B(n) = Σ S(n,k) for k=0 to n ll Bell_Stirling(int n) { ll res = 0; for (int k = 0; k <= n; k++) { res = (res + Stirling2(n, k)) % MOD; } return res; } // 贝尔数B(n),基于动态规划的实现,O(n^2) // 使用递推关系:B(n+1) = Σ C(n,k)*B(k) for k=0 to n ll Bell_DP(int n) { if (n == 0) return 1; vector bell(n + 1); bell[0] = 1; for (int i = 1; i <= n; i++) { bell[i] = 0; for (int k = 0; k < i; k++) { bell[i] = (bell[i] + C(i - 1, k) * bell[k]) % MOD; } } return bell[n]; } // 卡特兰数,O(1) ll Catalan(int n) { return C(2 * n, n) * inv(n + 1) % MOD; } // 错位排列数,O(n)预处理后O(1)查询 ll Derangement(int n) { if (n == 0) return 1; if (n == 1) return 0; // D(n) = (n-1)*(D(n-1)+D(n-2)) vector d(n + 1); d[0] = 1; d[1] = 0; for (int i = 2; i <= n; i++) { d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD; } return d[n]; } // 计算gcd,O(log min(a,b)) ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } // 计算lcm,O(log min(a,b)) ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } // 扩展欧几里得算法,求解ax + by = gcd(a,b) ll ext_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll d = ext_gcd(b, a % b, y, x); y -= a / b * x; return d; } // 中国剩余定理,求解x ≡ a_i (mod m_i) ll CRT(const vector &a, const vector &m) { ll M = 1, x = 0; int n = a.size(); for (int i = 0; i < n; i++) M *= m[i]; for (int i = 0; i < n; i++) { ll Mi = M / m[i]; ll y, z; ext_gcd(Mi, m[i], y, z); x = (x + a[i] * Mi % M * y % M) % M; } return (x + M) % M; } // 欧拉函数,计算小于n且与n互质的数的个数,O(sqrt(n)) ll EulerPhi(ll n) { ll res = n; for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { res = res / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) res = res / n * (n - 1); return res; } }; Combinatorics comb(1000000); // 预处理1e6以内的阶乘