对于每一个长度为 $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
样例输出
16