#P17766. [ICPC 2019 Yinchuan R] Crazy Cake

[ICPC 2019 Yinchuan R] Crazy Cake

1s 512M

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

2 
2 
3

输出 #1

2
4

说明/提示

下图展示了有 33 颗草莓时切蛋糕的 44 种方案。