#include using namespace std; #define int long long #define rep(i,n) for(int i=0, i##_len=(n); i istream& operator>>(istream& is, vector& vec) { for (T& x : vec) is >> x; return is; } // pair template ostream& operator<<(ostream& os, pair& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template ostream& operator<<(ostream& os, const vector& vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // map template ostream& operator<<(ostream& os, map& map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // set template ostream& operator<<(ostream& os, set& set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head&& head, Tail&& ... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #ifdef DEBUG #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \ << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif // http://beet-aizu.hatenablog.com/entry/2018/04/08/145516 template vector make_v(size_t a){return vector(a);} template auto make_v(size_t a,Ts... ts){ return vector(ts...))>(a,make_v(ts...)); } template typename enable_if::value==0>::type fill_v(T &t,const V &v){t=v;} template typename enable_if::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } #endif #define mod 1000000007 typedef pair P; #define INF (1LL<<60) void solve(){ int N, d, K; cin >> N >> d >> K; auto dp=make_v(N+1, N*d+1000); fill_v(dp,0); dp[0][0]=1; for(int i=0; i