fn main() { let mut io = IO::new(); input!{ from io, n: i64, k: i64, d: i64 } let a = (n - 2) / (k - 1); let m = n - (k - 1) * a; let fact = Fact::new((m + a) as usize, MOD); let s = (0..=a).map( |x| modpow(d, x, MOD) * fact.combination((m+a-x-2) as usize, (a-x) as usize) % MOD ).sum::() % MOD * m % MOD; io.println(if d == 1 { m } else { s }); } const MOD: i64 = 1_000_000_007; pub fn modpow(mut x: i64, mut y: i64, modulo: i64) -> i64 { x %= modulo; if x == 0 { return 0; } let mut ret = 1; let mut cur = x; while y > 0 { if y & 1 > 0 { ret = ret * cur % modulo; } cur = cur * cur % modulo; y >>= 1; } ret } pub struct Fact { modulo: i64, fact: Vec, inv_fact: Vec } impl Fact { pub fn new(size: usize, modulo: i64) -> Self { let mut fact = vec![1; size + 1]; let mut inv_fact = vec![1; size + 1]; for i in 1..size+1 { fact[i] = fact[i-1] * i as i64 % modulo; } inv_fact[size] = Self::modinv(fact[size], modulo); for i in (1..size+1).rev() { inv_fact[i-1] = inv_fact[i] * i as i64 % modulo; } Fact { modulo, fact, inv_fact } } pub fn extgcd(a: i64, b: i64) -> (i64, i64) { let mut x1 = 1; let mut y1 = 0; let mut m = a; let mut x2 = 0; let mut y2 = 1; let mut n = b; while m % n != 0 { let q = m / n; x1 -= q * x2; y1 -= q * y2; m -= q * n; std::mem::swap(&mut x1, &mut x2); std::mem::swap(&mut y1, &mut y2); std::mem::swap(&mut m, &mut n); } (x2, y2) } pub fn modinv(mut x: i64, modulo: i64) -> i64 { x = x.rem_euclid(modulo); Self::extgcd(x, modulo).0.rem_euclid(modulo) } pub fn permutation(&self, n:usize, r:usize) -> i64 { assert!(r > n || n < self.fact.len(), "index out of range: length is {}, but given {}", self.fact.len(), n); if n < r { return 0 }; self.fact[n] * self.inv_fact[n-r] % self.modulo } pub fn combination(&self, n:usize, r:usize) -> i64 { assert!(r > n || n < self.fact.len(), "index out of range: length is {}, but given {}", self.fact.len(), n); if n < r { return 0 }; self.fact[n] * self.inv_fact[r] % self.modulo * self.inv_fact[n-r] % self.modulo } pub fn multi(&self, l: &[usize]) -> i64 { let n = l.iter().sum::(); assert!(n < self.fact.len(), "index out of range: length is {}, but given {}", self.fact.len(), n); let mut ans = self.fact[n]; for &x in l { ans = ans * self.inv_fact[x] % self.modulo; } ans } } // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan(&mut self) -> ::Output { ::scan(self) } pub fn scan_vec(&mut self, n: usize) -> Vec<::Output> { (0..n).map(|_| self.scan::()).collect() } pub fn print(&mut self, x: T) { ::print(self, x); } pub fn println(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String, f32, f64); impl Scan for char { type Output = char; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().next().unwrap() } } pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::().wrapping_sub(1) } } impl Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize, f32, f64); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [[$kind:tt; $len1:expr]; $len2:expr] $($rest:tt)*) => { let $($mut)* $var = (0..$len2).map(|_| $io.scan_vec::<$kind>($len1)).collect::>>(); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------