李先生在生日时买了一个圆形的草莓蛋糕，糕点师在蛋糕周围均匀地放置了 $n$ 个相同的草莓。现在李先生想要按照以下规则切割蛋糕：
- 每一条切割轨迹必须是连接两个草莓的线段。
- 任意两条切割轨迹不能在蛋糕内部严格相交，但它们可以共享同一个草莓。
注意，切割轨迹允许连接两个相邻的草莓，李先生也可以选择不做任何切割。请你帮助李先生计算切割蛋糕的不同方案数。如果两种方案在旋转蛋糕后重合，则视为同一种方案。由于答案可能非常大，你只需要输出答案对 $1000000007$ 取模的结果。
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 每个测试用例包含一个整数 $n$ ($2 \le n \le 10^6$)，表示草莓的数量。
输出格式
对于每个测试用例，输出一个整数，表示切割蛋糕的不同方案数对 $1000000007$ 取模的结果。
样例
输入 1
2 2 3
输出 1
2 4
说明
下图展示了 $3$ 个草莓时切割蛋糕的 $4$ 种方案。
