package main import ( "bufio" "fmt" "os" "strconv" ) func configure(scanner *bufio.Scanner) { scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) } func getNextString(scanner *bufio.Scanner) string { scanned := scanner.Scan() if !scanned { panic("scan failed") } return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout extra := 0 if os.Getenv("I") == "IronMan" { fp, _ = os.Open(os.Getenv("END_GAME")) extra = 100 } scanner := bufio.NewScanner(fp) configure(scanner) writer := bufio.NewWriter(wfp) defer func() { r := recover() if r != nil { fmt.Fprintln(writer, r) } writer.Flush() }() solve(scanner, writer) for i := 0; i < extra; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { n := getNextInt(scanner) s := getNextInt(scanner) k := getNextInt(scanner) s -= (n - 1) * n * k / 2 if s < 0 { fmt.Fprintln(writer, 0) return } if s == 0 { fmt.Fprintln(writer, 1) return } dp := makeGrid(n+1, s+1) dp[1][1] = 1 for i := 1; i < n+1; i++ { for j := 1; j < s; j++ { if i < n { dp[i+1][j+1].AddAs(dp[i][j]) } if i+j < s+1 { dp[i][i+j].AddAs(dp[i][j]) } } } var ans Mint for i := 0; i < n+1; i++ { ans.AddAs(dp[i][s]) } fmt.Fprintln(writer, ans) } func makeGrid(h, w int) [][]Mint { index := make([][]Mint, h, h) data := make([]Mint, h*w, h*w) for i := 0; i < h; i++ { index[i] = data[i*w : (i+1)*w] } return index } // Mod constants. const ( Mod1000000007 = 1000000007 Mod998244353 = 998244353 ) var mod Mint = Mod1000000007 // Mint treats the modular arithmetic type Mint int64 // SetMod sets the mod. It must be called first. func SetMod(newmod Mint) { mod = newmod } // Mod returns m % mod. func (m Mint) Mod() Mint { m %= mod if m < 0 { return m + mod } return m } // Inv returns modular multiplicative inverse func (m Mint) Inv() Mint { return m.Pow(Mint(0).Sub(2)) } // Pow returns m^n func (m Mint) Pow(n Mint) Mint { p := Mint(1) for n > 0 { if n&1 == 1 { p.MulAs(m) } m.MulAs(m) n >>= 1 } return p } // Add returns m+x func (m Mint) Add(x Mint) Mint { return (m + x).Mod() } // Sub returns m-x func (m Mint) Sub(x Mint) Mint { return (m - x).Mod() } // Mul returns m*x func (m Mint) Mul(x Mint) Mint { return (m * x).Mod() } // Div returns m/x func (m Mint) Div(x Mint) Mint { return m.Mul(x.Inv()) } // AddAs assigns *m + x to *m and returns m func (m *Mint) AddAs(x Mint) *Mint { *m = m.Add(x) return m } // SubAs assigns *m - x to *m and returns m func (m *Mint) SubAs(x Mint) *Mint { *m = m.Sub(x) return m } // MulAs assigns *m * x to *m and returns m func (m *Mint) MulAs(x Mint) *Mint { *m = m.Mul(x) return m } // DivAs assigns *m / x to *m and returns m func (m *Mint) DivAs(x Mint) *Mint { *m = m.Div(x) return m }