定义长为 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。