Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

CP有N个糖,标号为1-N,还有N个糖盒,标号也为1-N,现在CP想把这些糖放在这些糖盒里,但是编号为i的糖不能放在编号为i的糖盒里,请问有多少中方法?

Input

第一行T表示数据的组数 接下来T组数据:每组开头一行N<=10000,含义如题。

Output

对于每组数据,输出一行,输出方法数 % 1000000007。

Sample Input

2 4714 2523

Sample Output

138579924 203446163