Start: 2024-03-04 00:00:00

(23-24赛季)稠州常规赛10

End: 2024-03-07 00:00:00
Now  2025-09-26 08:25:35  类型: ACM/ICPC  状态: Ended 

P5. 整数划分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


Submit

题目参数
Time Limit 1 second
Memory Limit 256 MB
Submit