题目描述

将正整数 $n$（$n \le 50000$）分成若干个互不相同的正整数的和，有多少种不同的划分方式？

例如：$n=6$ 时，合法的划分有 $\{6\},\{1,5\},\{2,4\},\{1,2,3\}$，共 $4$ 种。 由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

输入格式

一行一个正整数 $n$。

输出格式

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

输入输出样例 #1

6

4

说明/提示

对于 $40\%$ 的数据，$n \le 100$；
对于 $100\%$ 的数据，$n \le 50000$。