#pragma region competitive_programming #ifdef __LOCAL #define _GLIBCXX_DEBUG #endif #pragma GCC optimize("Ofast") #include #include namespace tomo0608 { std::istream& operator>>(std::istream& is, atcoder::modint998244353& a) { long long v; is >> v; a = v; return is; } std::ostream& operator<<(std::ostream& os, const atcoder::modint998244353& a) { return os << a.val(); } std::istream& operator>>(std::istream& is, atcoder::modint1000000007& a) { long long v; is >> v; a = v; return is; } std::ostream& operator<<(std::ostream& os, const atcoder::modint1000000007& a) { return os << a.val(); } template std::istream& operator>>(std::istream& is, atcoder::static_modint& a) { long long v; is >> v; a = v; return is; } template std::ostream& operator<<(std::ostream& os, const atcoder::static_modint& a) { return os << a.val(); } template std::istream& operator>>(std::istream& is, atcoder::dynamic_modint& a) { long long v; is >> v; a = v; return is; } template std::ostream& operator<<(std::ostream& os, const atcoder::dynamic_modint& a) { return os << a.val(); } // Binomial Coefficient of modint template struct BiCoef { std::vector fact_, inv_, finv_; int MAX_SIZE; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : MAX_SIZE(n+1), fact_(n+1, 1), inv_(n+1, 1), finv_(n+1, 1) { init(n+1); } constexpr void init(int n) noexcept { assert(n >= 1 && n < (int)1e8); fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].mod(); for (int i = 2; i < n; i++) { fact_[i] = fact_[i - 1] * i; inv_[i] = -inv_[MOD % i] * (MOD / i); finv_[i] = finv_[i - 1] * inv_[i]; } } constexpr mint com(long long n, long long k) const noexcept { if (n < k || n < 0 || k < 0)return 0; //if(n >= MAX_SIZE)return com_naive(n, k); return fact_[n] * finv_[k] * finv_[n - k]; } constexpr mint permi(int n, int k) const noexcept { if (n < k || n < 0 || k < 0)return 0; return fact_[n] * finv_[n - k]; } constexpr mint homo(int n, int r) { // The number of cases where k indistinguishable balls are put into n distinct boxes if (n < 0 || r < 0)return 0; return r == 0 ? 1 : com(n + r - 1, r); } constexpr mint second_stirling_number(int n, int r) { // The number of cases where n distinct balls are put into k indistinguishable boxes, with at least one ball in each box mint ret = 0; for (int i = 0; i <= r; i++) { mint tmp = com(r, i) * mint(i).pow(n); ret += ((r - i) & 1) ? -tmp : tmp; } return ret * finv_[r]; } constexpr mint bell_number(int n, int r) { // The number of cases where n distinct balls are put into k indistinguishable boxes if (n == 0) return 1; r = std::min(r, n); std::vector pref(r + 1); pref[0] = 1; for (int i = 1; i <= r; i++) { if (i & 1) { pref[i] = pref[i - 1] - finv_[i]; } else { pref[i] = pref[i - 1] + finv_[i]; } } mint ret = 0; for (int i = 1; i <= r; i++) ret += mint(i).pow(n) * fact_[i] * pref[r - i]; return ret; } constexpr mint fact(int n) const noexcept { if (n < 0)return 0; return fact_[n]; } constexpr mint inv(int n) const noexcept { if (n < 0)return 0; return inv_[n]; } constexpr mint finv(int n) const noexcept { if (n < 0)return 0; return finv_[n]; } inline mint operator()(long long n, long long k) { return com(n, k); } constexpr mint com_naive(long long n, long long k) { if (n < k || n < 0 || k < 0)return 0; mint res = 1; k = std::min(k, n - k); for (int i = 1; i <= k; i++)res *= inv(i) * (n--); return res; } }; } // namespace tomo0608 //typedef atcoder::modint1000000007 mint; typedef atcoder::modint998244353 mint; //#include //#include "Formal_Power_Series.hpp" //typedef tomo0608::Formal_Power_Series fps; namespace tomo0608 { typedef long long ll; typedef long double ld; template using V = std::vector; template using VV = V>; template using VVV = V>; typedef std::pair pii; typedef std::pair pll; templatevoid input(T&... a) { (std::cin >> ... >> a); }; #define INT(...) int __VA_ARGS__; IN(__VA_ARGS__) #define LL(...) long long __VA_ARGS__; IN(__VA_ARGS__) #define CHAR(...) char __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define DBL(...) double __VA_ARGS__; IN(__VA_ARGS__) #define VEC(type, name, size) std::vector name(size);IN(name) #define VECVEC(type, name, h, w) std::vector> name(h, std::vector(w));IN(name) template std::istream& operator>>(std::istream& is, std::pair& p) { is >> p.first >> p.second; return is; } template std::ostream& operator<<(std::ostream& os, const std::pair& p) { os << '(' << p.first << ", " << p.second << ')'; return os; } template std::istream& operator>>(std::istream& is, std::vector& v) { for (auto& e : v) is >> e; return is; } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { for (auto& e : v) os << e << ' '; return os; } template std::ostream& operator << (std::ostream& os, std::set& set_var) { os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr;++itr;if (itr != set_var.end()) os << ", ";itr--; }os << "}";return os; } template std::ostream& operator<<(std::ostream& os, std::map& map_var) { os << "{";for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << *itr;itr++;if (itr != map_var.end()) os << ", ";itr--; }os << "}";return os; } template void print_tuple(std::ostream&, const T&) {} template void print_tuple(std::ostream& os, const T& t) { if (i){os << ", ";} os << std::get(t); print_tuple(os, t); } template std::ostream& operator<<(std::ostream& os, const std::tuple& t) { os << "{"; print_tuple<0, std::tuple, Args...>(os, t); return os << "}"; } void IN() {} template void IN(Head& head, Tail &...tail) { std::cin >> head; IN(tail...); } void print() { std::cout << '\n'; } templatevoid print(const T& a, const Ts&... b) { std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout << '\n'; } void drop() { std::cout << '\n';exit(0); } templatevoid drop(const T& a, const Ts&... b) { std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout << '\n';exit(0); } #ifdef __LOCAL void debug_out() { std::cerr << std::endl; } template < class Head, class... Tail> void debug_out(Head H, Tail... T) { std::cerr << ' ' << H; debug_out(T...); } #define debug(...) std::cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) std::cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << std::endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif #define rep1(a) for(long long i = 0; i < (a); i++) #define rep2(i, a) for(long long i = 0; i < (a); i++) #define rep3(i, a, b) for(long long i = (a); i < (b); i++) #define rep4(i, a, b, c) for(long long i = (a); i < (b); i += (c)) #define drep1(a) for(long long i = (a)-1; i >= 0; i--) #define drep2(i, a) for(long long i = (a)-1; i >= 0; i--) #define drep3(i, a, b) for(long long i = (a)-1; i >= (b); i--) #define drep4(i, a, b, c) for(long long i = (a)-1; i >= (b); i -= (c)) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define drep(...) overload4(__VA_ARGS__, drep4, drep3, drep2, drep1)(__VA_ARGS__) #define endl '\n' struct io_setup { io_setup() { std::cin.tie(0); std::ios_base::sync_with_stdio(false); std::cout << std::setprecision(20); } }io_setup; } // namespace tomo0608 namespace tomo0608 { #define ALL(x) x.begin(),x.end() template T SUM(const S& v) { return accumulate(ALL(v), T(0)); } #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define SORT(v) sort(ALL(v)) #define REVERSE(v) reverse(ALL(v)) #define RSORT(v) sort(ALL(v)); reverse(ALL(v)) #define UNIQUE(x) SORT(x), x.erase(unique(ALL(x)), x.end()) #define lb(c, x) distance((c).begin(), lower_bound(ALL(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(ALL(c), (x))) template void zip(std::vector& x) { std::vector y = x;UNIQUE(y);for (int i = 0; i < x.size(); ++i) { x[i] = lb(y, x[i]); } } template using priority_queue_rev = std::priority_queue, std::greater>; template inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return 1; } return 0; } template inline int count_between(std::vector& a, T l, T r) { return lower_bound(ALL(a), r) - lower_bound(ALL(a), l); } // [l, r) template int bittest(T n, int k) { return (n >> k) & 1; } int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); } int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); } int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); } int lowbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); } #define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(ALL(v)));) template T ceil(T x, S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); } template T floor(T x, S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1))); } template std::vector id_sort(const std::vector& v, bool greater = false) { int n = v.size(); std::vector ret(n); std::iota(ALL(ret), 0); std::sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; }); return ret; } struct Random_Number_Generator { std::mt19937_64 mt; Random_Number_Generator() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {} // 区間 [l,r) の整数で乱数発生 int64_t operator()(int64_t l, int64_t r) { std::uniform_int_distribution dist(l, r - 1); return dist(mt); } // 区間 [0,r) の整数で乱数発生 int64_t operator()(int64_t r) { return (*this)(0, r); } } rng; struct Timer { std::chrono::system_clock::time_point start_time; Timer() { reset(); } void reset() { start_time = std::chrono::system_clock::now(); } int get_time() { std::chrono::system_clock::time_point now_time = std::chrono::system_clock::now(); return std::chrono::duration_cast(now_time - start_time).count(); } } timer; } using namespace atcoder; using namespace std; using namespace tomo0608; int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }; int dy[8] = { 0, 1, 0, -1, 1, -1, -1, 1 }; // インタラクティブ問題のときは出力するたびにcout.flush();を忘れない!!!!! void solve(); int main() { int codeforces = 1; //cin >> codeforces; while (codeforces--) { solve(); } return 0; } #pragma endregion void solve() { LL(n, m, k); V dp(n+1); BiCoef bc(1000); for(int i = 0; i <= n; i++)dp[i] = bc.com(n, i); rep(i,m-1){ V ndp(n+1); rep(j, k, n+1){ rep(l, k, n+1){ // n個のうちjことlこが1 // sこ共通させる rep(s, k, min(j, l)+1){ ndp[l] += dp[j] * bc.com(j, s) * bc.com(n-j, l-s); } } } swap(dp, ndp); } mint ans = 0; for(auto x: dp)ans += x; print(ans); }