新年快乐 。゚・ (⁄ ⁄>⁄ ︿ ⁄<⁄ ⁄) ・゚。

1893. OEIS

定义长为 n 的集合的划分方法数为 B_n,如 B_3=5,因为 (a,b,c) 可以划分为 ((a),(b),(c)),((a),(b,c)),((b),(a,c)),((c),(a,b)),((a,b,c))。而 B_0=1 因为空集恰好有一种划分方法。可知前几项为 B_0=1,B_1=1,B_2=2,B_3=5,B_4=15

给定 n,求 B_n

输入

输入一行一个整数 n(0\le n\le25)

输出

输出一行一个整数 B_n

样例

标准输入 复制文本
0
标准输出 复制文本
1
标准输入 复制文本
3
标准输出 复制文本
5
标准输入 复制文本
25
标准输出 复制文本
4638590332229999353

提示

自主思考:如果结果对 10^9+7 取模下,① n\le10^3,② n\le10^5,如何计算 B_n

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 11
通过 8