题号：NC25672
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
对于一张无向连通图 G ，选定一个点 s 作为起点进行深度优先遍历，假设当前位于点 u，选出和 u 有边直接相连的之前未访问过的编号最小的点 v，递归到 v 继续进行深度优先遍历，如果找不到这样的点 v 则回溯。整个遍历过程结束后会得到一个序列，表示每个点第一次被访问的顺序。
（没有伪代码）
（没有伪代码）
现在你需要找出所有带标号的仙人掌，点从 1 到 n 标号，满足以点 1 作为起点进行深度优先遍历得到的遍历序列恰好就是 1, 2, 3, ..., n，并给出满足条件的仙人掌的方案数。由于方案数可能很大，你只需要输出方案数对 1000000007 取模后的值。
这里仙人掌是指一个无向的连通图，这个图不存在自环，且任意一条边至多属于一个简单环。所谓简单环，是指在图中任取一个顶点作为起点，沿着不重复的边、经过不重复的点再次走到起点的闭合路径。两个仙人掌是不同的，当且仅当存在某一条边属于其中恰好一个仙人掌。
输入描述:
第一行包含一个整数T
(1 <= T <= 5000)，表示测试数据的组数，
每组测试数据都只有一行，包含一个整数n (1
<= n <= 5000)，表示仙人掌的点数。
输出描述:
对于每组测试数据，输出一行，包含一个整数，表示满足条件的仙人掌的方案数对
1000000007 取模后的值。