#398. 整数划分

    ID: 398 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>动态规划完全背包计数DP整数划分CF

整数划分

整数划分

题目描述

一个正整数 nn 可以表示为若干个正整数的和:

n=n1+n2+⋯+nk,n = n_1 + n_2 + \cdots + n_k,

其中 n1≥n2≥⋯≥nkn_1 \ge n_2 \ge \cdots \ge n_k 且 k≥1k\ge 1。

每一种满足以上条件的表示,都称为正整数 nn 的一种划分。请计算 nn 有多少种不同的划分方式。

由于答案可能很大,请将答案对 109+710^9+7 取模后输出。

输入格式

输入共一行,包含一个正整数 nn。

输出格式

输出一行,包含一个整数,表示 nn 的不同划分方式数量对 109+710^9+7 取模的结果。

数据范围

1≤n≤10001\le n\le 1000。

输入样例

5

输出样例

7

样例解释

55 的 77 种划分如下(不区分相加顺序):

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

同一种划分中的各部分必须为正整数,排列顺序不同不视为不同划分。