P17644 [ICPC 2019 Yinchuan R] Crazy Cake
题目描述
李先生在生日时买了一个圆形的草莓蛋糕，糕点师傅将 $n$ 颗完全相同的草莓均匀地摆放在蛋糕周围。现在李先生想按照以下规则切分蛋糕：
- 每一刀切痕必须是连接两颗草莓的线段。
- 任意两条切痕不能在蛋糕内部严格相交，但它们可以共享同一颗草莓。
注意，切痕可以连接两颗相邻的草莓，李先生也可以一刀都不切。
请你帮助李先生计算切蛋糕的不同方案数。如果两个方案可以通过旋转蛋糕而重合，则认为它们相同。由于答案可能非常大，你只需要输出答案对 $1000000007$ 取模的结果。
输入格式
第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试数据的组数。
每组测试数据包含一个整数 $n~(2 \leq n \leq 10^6)$，表示草莓的数量。
输出格式
对于每组测试数据，输出一个整数，表示切蛋糕的不同方案数对 $1000000007$ 取模的结果。
说明/提示
下图展示了有 $3$ 颗草莓时切蛋糕的 $4$ 种方案。
:::align{center}
:::
翻译由 DeepSeek V4 Pro 完成