1. 状态表示 f[i][j], 正整数 i 的划分中以 j 为最大值的划分数
2. 状态转移方程 $$f[i][j] = sum_{t=1}^{j}f[i-j][t] $$
3. 此时时间复杂度为$o(n^3)$需要优化
4. 使用 s[N][N] 来记录第 i 行的前缀和

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var (
    ot = bufio.NewWriter(os.Stdout)
    in = bufio.NewReader(os.Stdin)
)

func rS() (s string)                         { _, _ = fmt.Fscan(in, &s); return }
func rI() int                                { i, _ := strconv.Atoi(rS()); return i }
func rF() float64                            { f, _ := strconv.ParseFloat(rS(), 64); return f }
func print(a ...interface{})                 { _, _ = fmt.Fprint(ot, a...) }
func println(a ...interface{})               { _, _ = fmt.Fprintln(ot, a...) }
func printf(format string, a ...interface{}) { _, _ = fmt.Fprintf(ot, format, a...) }
func max(a ...int) int {
    m := a[0]
    for i := 1; i < len(a); i++ {
        if a[i] > m {
            m = a[i]
        }
    }
    return m
}

func min(a ...int) int {
    m := a[0]
    for i := 1; i < len(a); i++ {
        if a[i] < m {
            m = a[i]
        }
    }
    return m
}

// -------------------------------------------------------
const N = 1010
const p = 1e9 + 7

var f [N][N]int
var s [N][N]int

// --------------------------------------------------------

func main() {
    defer func(ot *bufio.Writer) {
        _ = ot.Flush()
    }(ot)
    // solve
    n := rI()
    for i := 0; i <= n; i++ {
        s[0][i] = 1
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= i; j++ {
            f[i][j] = s[i-j][j]
        }
        for j := 1; j <= n; j++ {
            s[i][j] = (f[i][j] + s[i][j-1]) % p
        }
    }
    ans := 0
    for i := 1; i <= n; i++ {
        ans = (ans + f[n][i]) % p
    }
    println(ans)
}