You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

聪明hao_pp最近正在学习高数，marble这天打算为难一下hao_pp,现在假设有一个长度为$n$的数组，这个数组没有相同的数字，现在需要对这个数组中的数字两两分组，问有多少种分组的方式。注意分出的组没有次序因此只要划分方式相同算一种分组。因为给出的$n$特别大,请你写出一个程序来帮助hao_pp计算结果,答案对$1e9+7$取模

Input Format

多组询问，第一行输入一个整数$t$代表询问数，后面$t$行每行一个整数$n$表示数组的大小

Output Format

共$t$行每行一个整数表示答案

Sample

样例输入

1
4

样例输出

3

Hint

样例解释： 共一组询问，假设输入的数组为[1,2,3,4]那么两两组合的方式一共有3 种：

第一种 (1,2),(3,4)

第二种 (1,3),(2,4)

第三种 (1,4)(2,3)

因此答案为3

$1\leq t \leq 2*10^5$

$2\leq n \leq 2*10^5$,且$n$为偶数