use modint::ModInt; #[allow(unused_imports)] use std::io::Write; // {{{1 #[allow(unused)] macro_rules! debug { ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap()); } #[allow(unused)] macro_rules! debugln { ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap()); } macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // }}} fn main() { input! { n: usize, d: usize, k: usize, } let mut solve = Solve { d, memo: vec![vec![None; d * n + 1]; n + 1], }; println!("{}", solve.solve(n, k).0); } struct Solve { d: usize, memo: Vec>>, } impl Solve { fn solve(&mut self, n: usize, k: usize) -> ModInt { if let Some(a) = self.memo[n][k] { return a } if n == 0 { if k == 0 { let ret = ModInt::from(1); self.memo[n][k] = Some(ret); return ret } else { let ret = ModInt::from(0); self.memo[n][k] = Some(ret); return ret } } let mut ret: ModInt = 0.into(); for i in 1..=self.d { if k >= i { ret += self.solve(n - 1, k - i); } } self.memo[n][k] = Some(ret); ret } } mod modint { use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign}; pub const MODULO: usize = 1_000_000_007; // pub const MODULO: usize = 11; fn positive_rem(a: isize, b: usize) -> usize { let b = b as isize; let mut value = a % b; if value < 0 { value += b; } // TODO: TryFrom value as usize } /// Return (x, y) s.t. ax + by = d where d = gcd(a, b) #[allow(unused)] pub fn ext_gcd(a: usize, b: usize) -> (isize, isize) { if b == 0 { return (1, 0); } let q = (a / b) as isize; let r = a % b; let (x1, y1) = ext_gcd(b, r); (y1, x1 - q * y1) } #[derive(Debug, Copy, Clone)] pub struct ModInt(pub usize); impl From for ModInt { fn from(n: usize) -> ModInt { ModInt(n % MODULO) } } impl From for ModInt { fn from(n: isize) -> ModInt { // TODO: use TryFrom ModInt(positive_rem(n, MODULO as usize)) } } impl From for ModInt { fn from(n: i32) -> ModInt { // TODO: use TryFrom ModInt(positive_rem(n as isize, MODULO as usize)) } } impl ModInt { #[allow(unused)] pub fn pow(self, p: usize) -> ModInt { if self == ModInt::from(0) { return ModInt::from(0); } if p == 0 { return ModInt::from(1); } if p % 2 == 0 { let half = self.pow(p / 2); half * half } else { self.pow(p - 1) * self } } // when MODULO is prime #[allow(unused)] pub fn inv(self) -> ModInt { let (x, _) = ext_gcd(self.0 as usize, MODULO as usize); ModInt::from(x) } } impl Add for ModInt { type Output = ModInt; fn add(self, other: ModInt) -> ModInt { ModInt::from(self.0 + other.0) } } impl Sub for ModInt { type Output = ModInt; fn sub(self, other: ModInt) -> ModInt { ModInt::from(self.0 as isize - other.0 as isize) } } impl Mul for ModInt { type Output = ModInt; fn mul(self, other: ModInt) -> ModInt { ModInt::from(self.0 * other.0) } } impl Neg for ModInt { type Output = ModInt; fn neg(self) -> Self::Output { ModInt::from(0) - self } } impl AddAssign for ModInt { fn add_assign(&mut self, other: Self) { *self = *self + other; } } impl MulAssign for ModInt { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } impl SubAssign for ModInt { fn sub_assign(&mut self, other: Self) { *self = *self - other; } } impl PartialEq for ModInt { fn eq(&self, &other: &Self) -> bool { self.0 == other.0 } } impl Eq for ModInt {} #[derive(Debug)] pub struct ModIntUtil { factorial: Vec, factorial_inv: Vec, inv: Vec, } impl ModIntUtil { #[allow(unused)] pub fn new() -> ModIntUtil { ModIntUtil { factorial: vec![ModInt::from(1), ModInt::from(1)], factorial_inv: vec![ModInt::from(1), ModInt::from(1)], inv: vec![ModInt::from(0), ModInt::from(1)], } } fn calc_cache(&mut self, n: usize) { let len = self.factorial.len(); if len < n + 1 { for i in len..(n + 1) { let prev = *self.factorial.last().unwrap(); self.factorial.push(prev * ModInt::from(i)); let inv_i = -self.inv[MODULO % i] * ModInt::from(MODULO / i); self.inv.push(inv_i); let prev = *self.factorial_inv.last().unwrap(); self.factorial_inv.push(prev * self.inv[i]); } } } #[allow(unused)] pub fn factorial(&mut self, n: usize) -> ModInt { self.calc_cache(n); self.factorial[n] } #[allow(unused)] pub fn factorial_inv(&mut self, n: usize) -> ModInt { self.calc_cache(n); self.factorial_inv[n] } // when MODULO is prime #[allow(unused)] pub fn binom_coef(&mut self, n: usize, k: usize) -> ModInt { if n < k { return ModInt::from(0); } self.calc_cache(n); self.factorial[n] * self.factorial_inv[k] * self.factorial_inv[n - k] } #[allow(unused)] fn perm(&mut self, n: usize, k: usize) -> ModInt { if n < k { return ModInt::from(0); } self.factorial(n) * self.factorial_inv(n - k) } // Not tested!! #[allow(unused)] pub fn multi_coef(&mut self, v: &[usize]) -> ModInt { let n = v.iter().sum(); self.calc_cache(n); let mut ret = ModInt::from(1); ret *= self.factorial[n]; for v_i in v { ret *= self.factorial_inv[*v_i]; } ret } } }