对于每一个长度为 $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