问题 1416. -- 小鸟的修路计划

1416: 小鸟的修路计划

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

题目描述

从前有m个独立的国家,它们想修一些路,使任意两个国家互相可达。于是,各国的首脑聚在一起开会,商议如何修路。此时,最富裕的国家——N国的首脑小鸟站出来说:“讨论如何修路没有意思,我们来想一下有多少种修法吧。”可是他并没有想出问题的答案,所以他想请教你,有多少种不同的修路方案能使这m个国家相互可达。
注意: 两个国家之间不应该修多条路,且不应该有一条路自己连向自己——这没有任何意义,你能明白的

输入

输入一个正整数T表示数据组数。
接下来T行,每行一组数据,输入一个正整数m,表示国家数。

输出

对于每个m输出一行,表示方案数。
注意答案可能很大,所以需要将答案对 10^9+7 取模。

样例输入

2
1
3

样例输出

1
4

提示

1<=T<=10


1<=m<=1000

来源

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