题目描述

李先生在生日时买了一个圆形的草莓蛋糕，糕点师傅将 $n$ 颗完全相同的草莓均匀地摆放在蛋糕周围。现在李先生想按照以下规则切分蛋糕：

• 每一刀切痕必须是连接两颗草莓的线段。
• 任意两条切痕不能在蛋糕内部严格相交，但它们可以共享同一颗草莓。

注意，切痕可以连接两颗相邻的草莓，李先生也可以一刀都不切。

请你帮助李先生计算切蛋糕的不同方案数。如果两个方案可以通过旋转蛋糕而重合，则认为它们相同。由于答案可能非常大，你只需要输出答案对 $1000000007$ 取模的结果。

输入格式

第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试数据的组数。

每组测试数据包含一个整数 $n~(2 \leq n \leq 10^6)$，表示草莓的数量。

输出格式

对于每组测试数据，输出一个整数，表示切蛋糕的不同方案数对 $1000000007$ 取模的结果。

2 
2 
3

2
4

提示

下图展示了有 $3$ 颗草莓时切蛋糕的 $4$ 种方案。

:::align{center} :::

翻译由 DeepSeek V4 Pro 完成