主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 D: Too Stupid

问题 D: Too Stupid

时间限制: 1 Sec  内存限制: 128 MB
提交: 105  解决: 42
[提交][状态][讨论版]

题目描述

某天 light由于太富而且太帅遭到了歹徒的袭击,现在他遇到了n个歹徒,准备对light施行不法行为,虽然light身体强壮,但是毕竟只有一个人肯定打不过那么多歹徒,但是高智商的light觉得歹徒们非常stupid,不打算束手就擒。经过观察他发现这些歹徒是有派系之分的
我们规定 A与B,B与C为同一个派系,那么A与C也为同一个派系
light认为,如果了解了歹徒的派系情况,他就可以用一些特殊的计谋战胜他们。但是,歹徒之间形成派系的可能性很多,而light对此一无所知。
现在问题来了,歹徒们有多少种可能形成派系的方案呢。由于方案数可能会很大,请对1000000007取模后输出。

输入

多组数据,处理到EOF

每组数据 第一行整数n       1 <= n <=1000

输出

输出方案数, 并对1000000007(1e9+7)取模

样例输入

1
2
3

样例输出

1
2
5

提示

 三个歹徒的情况:


1:A与B同派系,C不同


2:B与C同派系,A不同


3:A与C同派系,B不同


4:A,B,C三人同派系


5:A,B,C三人都不同派系


[提交][状态][讨论版]