1891 - 整数划分2
描述

将整数n进行划分,且每份不能为空,任意两个方案不相同(不考虑顺序),且划分的时候,不能有相同的数。

例如:n=6,下面三种分法被认为是相同的。

1,2,3;

3,1,2;

3,2,1;

问有多少种不同的分法。



输入

一个数字,表示将要被划分的数字

输出

一个数字表示能划分的方案数 mod 10^9+7

样例

输入

6

输出

4
提示

1,2,3;

1,5;

2,4;

6;

1 \leq n \leq 100

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 12
通过次数 10