小鸟的修路计划-j9国际集团直营

1416: 小鸟的修路计划

时间限制: 1000 ms  内存限制: 128 MB
提交: 297  解决: 67
[提交][状态][讨论版]

题目描述

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

输入

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

输出

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

样例输入

2
1
3

样例输出

1
4

提示

1<=T<=10

1<=m<=1000

来源

2019校赛online

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