该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T2. 整数拆分 (split)

题目描述

将正整数 $N$ 拆分为若干个正整数之和，有多少种不同的拆分方法？

两种拆分方法视为相同，当且仅当它们包含的正整数集合（多重集）相同，即顺序无关。例如 $4$ 的拆分有 $5$ 种：

• $4 = 4$
• $4 = 3 + 1$
• $4 = 2 + 2$
• $4 = 2 + 1 + 1$
• $4 = 1 + 1 + 1 + 1$

注意 $3+1$ 和 $1+3$ 算同一种。

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

输入格式

一行一个正整数 $N$。

输出格式

一行一个整数，表示拆分方案数模 $10^9+7$。

样例

样例 #1

4

5

数据范围

对于全部数据，$1\le N\le 5000$。