module main; // https://mayokoex.hatenablog.com/entry/2015/08/22/091536 より // 動的計画法 import std; // https://forum.dlang.org/post/k1js2b$1bef$1@digitalmars.com より // 変数の参照 struct Ref(T) { private T* _payload; this(ref T i) { _payload = &i; } @property ref T deref() { return *_payload; } alias deref this; } auto ref_(T)(ref T arg) { return Ref!T(arg); } // 多次元配列をある値で埋める void fill(A, T)(ref A a, T value) if (isArray!A) { alias E = ElementType!A; static if (isArray!E) { foreach (ref e; a) fill(e, value); } else { a[] = value; } } int N, S, K; immutable MOD = 10L ^^ 9 + 7; long[][] dp; long dfs(int n, int y) { if (y < 0) return 0; if (n == N - 1) return 1; auto ret = ref_(dp[n][y]); if (ret >= 0) return ret; ret = 0; for (int i = 0; i * (N - n) <= y; i++) { ret += dfs(n + 1, y - i * (N - n)); } ret %= MOD; return ret; } void main() { // 入力 readln.chomp.formattedRead("%d %d %d", N, S, K); // 答えの計算 S -= N * (N - 1) / 2 * K; dp = new long[][](101, 20_001); fill(dp, -1); // 答えの出力 writeln(dfs(0, S)); }