Good Permutations

题目描述

对于每一个长度为 $n$ 的排列 $a$ ，我们都可以按照下面的两种方式将它建成一个图：

1.对于每一个 $1\le i \le n$ ，找到一个最大的 $j$ 满足 $1\le j < i, a_j>a_i$ ，将 $i$ 和 $j$ 之间建一条无向边

2.对于每一个 $1\le i \le n$ ，找到一个最小的 $j$ 满足 $i< j \le n, a_j>a_i$ ，将 $i$ 和 $j$ 之间建一条无向边

注意：建立的边是在对应的下标 $i,j$ 之间建的边

请问有多少种长度为 $n$ 的排列 $a$ 满足，建出来的图含环

排列的数量可能会非常大，请输出它模上 $10^9+7$ 后的值

第 $1$ 行给出 $1$ 个数 $T(1\le T\le 10^5)$ ，表示有 $T$ 组测试样例

第 $2$ 到 $T+1$ 行每行给出一个数 $n(3\le n\le 10^6)$ ，表示排列的长度

输出符合条件的排列的数量模上 $10^9+7$ 后的值

1
4