Combinatorial mathematics once more

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

如果你对组合数学有所涉猎,你一定会对组合划分非常熟悉,那么问题来了:现在给你一个数集S的大小n,请告诉我将它划分为集合的方法总数ans是多少?
 

Input

 多组数据输入,每组输入有一个n(n<=5000)

Output

 首先请输出Case #x,表示当前为第x个样例,然后输出ans的值,也许答案会很大,所以请输出ans%(1e9+7)

Sample Input

3

Sample Output

Case #1: 5

Hint

 n=3,ans=5,
具体方法有如下几种:
{{a}, {b}, {c}}
{{a}, {b, c}}
{{b}, {a, c}}
{{c}, {a, b}}
{{a, b, c}}

Source

HDU shadow95