1556 - 整数划分easy
Description

将 N 分为若干个不同整数的和,有多少种不同的划分方式,例如: n=6 ,{6} {1,5},{2,4}{1,2,3} ,共 4种。由于数据较大,输出 1e9+7的结果即可。


Input

输入一个数字n,n<=1000

Output

输出划分的数量 (取模后的而结果) 。


Examples

Input

6

Output

4
Hint

10%,n<=10

40%,n<=100

100%,n<=1000

Tags
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 151
通过次数 67