有n封信,编号为1、2、...、n-1、n.

有n个信封,编号为1、2、...、n-1、n.

现在要把信装在信封里, 要求每个信封只能装一封信, 每封信都要装在与它编号不同的信封里, 求有多少种装信的方法。

由于答案可能很大，请输出答案对1e9+7取模。

输入：输入第一行为一个整数t (1<=t<=1e5)

接下来t行，每行一个整数n (1<=n<=1e5)

输出：共t行，每行一个整数，问题的答案。

末尾有换行

样例：

3

1

2

3

输出：

0

1

2