use std::fmt; use std::io::stdin; use std::io::BufRead; use std::str; use std::str::FromStr; const M:usize = 1000_000_007; fn main() { let stdin = stdin(); let mut scan = InputScanner::new(stdin.lock(),256); let n:usize = scan.next(); let s:usize = scan.next(); let k:usize = scan.next(); let m = n; let d:usize = (n * (n - 1)) / 2 * k; if d > s { println!("0"); } else { let n = s - d; let mut dp: Vec> = (0..(n + 1)).map(|_| (0..(m + 1)).map(|_| 0).collect()).collect(); dp[0][0] = 1; for j in 1..(m + 1) { for i in 0..(n + 1) { if i >= j { dp[i][j] = (dp[i - j][j] + dp[i][j - 1]) % M; } else { dp[i][j] = dp[i][j - 1]; } } } println!("{}", dp[n][m]); } } struct InputScanner { reader: R, buf: Vec, // Should never be empty pos: usize, // Should never be out of bounds as long as the input ends with '\n' } impl InputScanner { fn new(reader: R, capacity: usize) -> Self { InputScanner { reader: reader, buf: Vec::with_capacity(capacity), pos: 0, } } #[inline] fn next(&mut self) -> T where T::Err: fmt::Debug, { if self.buf.is_empty() { self._read_next_line(); } let mut start = None; loop { match (self.buf[self.pos], start.is_some()) { (b' ', true) | (b'\n', true) | (b'\r', true) => break, (_, true) | (b' ', false) => self.pos += 1, (b'\n', false) | (b'\r', false) => self._read_next_line(), (_, false) => start = Some(self.pos), } } let target = &self.buf[start.unwrap()..self.pos]; unsafe { str::from_utf8_unchecked(target) }.parse().unwrap() } #[inline] fn _read_next_line(&mut self) { self.pos = 0; self.buf.clear(); if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 { panic!("Reached EOF"); } } }