0205算法提高(1)期末测试

P3. 整数划分

描述

一个正整数可以表示成若干个正整数之和，形如： $n$ = $n_1+n_2+ \dots n_k$ ，其中 $n1>=n2>=........>=nk$ 。

我们将这样的一种表示称为正整数 $n$ 的一种划分。

现在给定一个正整数，请你求出 $n$ 共有多少种不同的划分方法。

输入

共一行，包含一个整数 $n$ 。

输出

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 $10^9+7$ 取模

样例

提示

30%数据： $1\leq n \leq 15$

100%数据： $1\leq n \leq 1000$

11111

1112

113

122

提交

题目参数

时间限制	1 秒
内存限制	128 MB