问题 1112. -- Too Stupid

1112: Too Stupid

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

题目描述

某天 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三人都不同派系


来源

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