题目描述

小蓝是幼儿园的老师，他的班上有 $N$ 个孩子，今天他和孩子们一起进行了一个游戏。

小蓝所在的学校是寄宿制学校，$N$ 个孩子分别有一个自己的房间，每个房间对应一把钥匙，每把钥匙只能打开自己的门。现在小蓝让这 $N$ 个孩子分别将自己宿舍的钥匙上交，再把这 $N$ 把钥匙随机打乱分给每个孩子一把钥匙，有 $N! = N × (N-1) × · · · × 1$ 种分配方案。小蓝想知道这些方案中，有多少种方案恰有一半的孩子被分到自己房间的钥匙（即有 $N/2$ 个孩子分到的是自己房间的钥匙，有 $N/2$ 个孩子分到的不是自己房间的钥匙）。

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 1 个整数 $N$。

输出描述

对每个输入输出一个整数表示答案，由于答案可能很大，输出除以 $10^9+7$ 的余数即可。。

2
40
28

845559995
336228739

评测用例规模与约定：

对于所有评测用例，$1≤T≤10，1≤N≤1000$。