#include <bits/stdc++.h> using namespace std; #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5/DPL_5_G" #include "../math/bell_number.cpp" #include "../math/mint.cpp" using mint2 = ModInt<1000000007>; int main() { int n, k; cin >> n >> k; BellNumber<mint2> bell(n, k); cout << bell.solve() << '\n'; return 0; }
#line 1 "test/bell_number.test.cpp" #include <bits/stdc++.h> using namespace std; #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5/DPL_5_G" #line 3 "math/bell_number.cpp" using namespace std; #line 3 "math/stirling_number2.cpp" using namespace std; // StirlingNumber2 // n個の区別できるものをk個の区別できない箱に1個以上に分割する方法が何通りあるか求める. // これをS(n,k)とする. 第二種スターリング数 template <typename T> struct StirlingNumber2 { int n, k; vector<vector<T>> dp; StirlingNumber2(int n, int k) : n(n), k(k) { dp.assign(n + 1, vector<T>(k + 1, T(0))); } // solve // S(i,j) (0 <= i <= n, 0 <= j <= k)を求める. // 計算量: O(nk) T solve() { dp[0][0] = T(1); for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { dp[i][j] = T(j) * dp[i - 1][j]; if (j > 0) dp[i][j] += dp[i - 1][j - 1]; } } return dp[n][k]; } // S(i,j)を返す. // 制約: 0 <= i <= n, 0 <= j <= k T operator()(int i, int j) { return dp[i][j]; } }; #line 6 "math/bell_number.cpp" /** * BellNumber * n個の区別できるものをk個の区別できない箱に0個以上に分割する方法が何通りあるか求める. * これをB(n,k)としてベル数という. */ template <typename T> struct BellNumber { int n, k; vector<vector<T>> dp; BellNumber(int n, int k) : n(n), k(k) { dp.assign(n + 1, vector<T>(k + 1, T(0))); } /** * solve * 0 <= i <= n,0 <= j <= kについてB(i,j)を求める. * 計算量: O(nk) */ T solve() { StirlingNumber2<T> s2(n, k); s2.solve(); for (int i = 0; i <= n; i++) { for (int j = 1; j <= k; j++) { dp[i][j] = dp[i][j - 1] + s2(i, j); } } return dp[n][k]; } /** * operator() * @param i int * @param j int * B(i,j) を返す. * 制約: 0 <= i <= n,0 <= j <= k */ T operator()(int i, int j) { return dp[i][j]; } }; #line 3 "math/mint.cpp" using namespace std; template <int MOD> struct ModInt { public: long long x; ModInt(long long x = 0) : x((x % MOD + MOD) % MOD) {} constexpr ModInt &operator+=(const ModInt a) noexcept { if ((x += a.x) >= MOD) x -= MOD; return *this; } constexpr ModInt &operator-=(const ModInt a) noexcept { if ((x += MOD - a.x) >= MOD) x -= MOD; return *this; } constexpr ModInt &operator*=(const ModInt a) noexcept { (x *= a.x) %= MOD; return *this; } constexpr ModInt &operator/=(const ModInt a) noexcept { return *this *= a.inverse(); } constexpr ModInt operator+(const ModInt a) const noexcept { return ModInt(*this) += a.x; } constexpr ModInt operator-(const ModInt a) const noexcept { return ModInt(*this) -= a.x; } constexpr ModInt operator*(const ModInt a) const noexcept { return ModInt(*this) *= a.x; } constexpr ModInt operator/(const ModInt a) const noexcept { return ModInt(*this) /= a.x; } friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt<MOD> a) noexcept { return os << a.x; } friend constexpr std::istream &operator>>(std::istream &is, ModInt<MOD> &a) noexcept { is >> a.x; a.x = (a.x % MOD + MOD) % MOD; return is; } ModInt inverse() const noexcept { // x ^ (-1) long long a = x, b = MOD, p = 1, q = 0; while (b) { long long d = a / b; a -= d * b; swap(a, b); p -= d * q; swap(p, q); } return ModInt(p); } ModInt pow(long long N) const noexcept { // x ^ N ModInt a = 1; ModInt y = this->x; while (N) { if (N & 1) a *= y; y *= y; N >>= 1; } return a; } }; template <typename U, int MOD> inline ModInt<MOD> operator*(const U &c, const ModInt<MOD> &a) { return {c * a.x}; } using mint = ModInt<998244353>; #line 7 "test/bell_number.test.cpp" using mint2 = ModInt<1000000007>; int main() { int n, k; cin >> n >> k; BellNumber<mint2> bell(n, k); cout << bell.solve() << '\n'; return 0; }