#398. 整数划分
整数划分
整数划分
题目描述
一个正整数 可以表示为若干个正整数的和:
其中 且 。
每一种满足以上条件的表示,都称为正整数 的一种划分。请计算 有多少种不同的划分方式。
由于答案可能很大,请将答案对 取模后输出。
输入格式
输入共一行,包含一个正整数 。
输出格式
输出一行,包含一个整数,表示 的不同划分方式数量对 取模的结果。
数据范围
。
输入样例
5
输出样例
7
样例解释
的 种划分如下(不区分相加顺序):
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
同一种划分中的各部分必须为正整数,排列顺序不同不视为不同划分。