1893 - 整数划分3
Description

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

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

1,2,3;

3,1,2;

3,2,1;

问有多少种不同的分法。




Input

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

Output

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

Examples

Input

6

Output

4
Hint

1,2,3;

1,5;

2,4;

6;

1 \leq n \leq 5\times 10^4


题目参数
Time Limit 1 second
Memory Limit 256 MB
提交次数 33
通过次数 12