SP16307 GOSTONES - Game of stones II

_**\[本题的简化版曾在 2013 年的阿根廷编程竞赛中使用，可以在尝试这道题之前先解那个版本：[http://www.spoj.com/problems/TAP2013J/](../../TAP2013J/ "TAP2013J") \]**_ Jaimito 喜欢用他生日得到的 **N** 块石头搭建各种不同大小的石堆。如果不是每到一天结束时，母亲 Jimena 总是提醒他要进行「整理石堆」（TAP），他会非常开心。在 TAP 时间，Jaimito 必须拆掉他辛苦堆起来的石堆。 Jimena 知道 Jaimito 不喜欢 TAP，于是提议和他一起做个游戏，让这个过程更有趣。Jaimito 和他的母亲轮流进行游戏，由于 Jaimito 年纪最小，所以他先开始。游戏一开始，会有一个或多个石堆，每个石堆都包含若干块石头。在每次轮到的回合中，玩家需要选择一个有两块以上石头的石堆，将其分成两个小石堆，且这两个小石堆可以不等大。如此反复，直到某一位玩家无法进行有效分割为止，此时不能继续的玩家便是输家，另一位则为赢家。 Jaimito 是个聪明的孩子，他发现可以通过策略性地分配这些石头，来保证他在游戏中先胜。Jaimito 认为如果两个初始石堆的排列仅在顺序上不同，则视为相同分布。也就是说，只有当石堆的数量不同，或相同数量的石堆中石头的分配方式不同，才算不同的组合。比如，当 **N = 4** 时，有五种方式可以排列它们：四个每个包含一个石头的石堆；两个包含一个石头的石堆和另一个包含两个石头的石堆；一个包含一个石头的石堆和另一个包含三个石头的石堆；两个各包含两个石头的石堆；最后，一整个石堆，包含所有四块石头。 Jaimito 不想让母亲察觉到他的策略，所以他想每天更换石头的初始分布。他觉得有很多方法可以确保自己获胜，只是不清楚具体有多少种。在 **N = 4** 的情况下，Jaimito 仅有两种能保证胜利的选择：所有石头堆成一堆，或者一个石堆有两个石头，另两个石堆各有一个石头。你的任务就是帮助 Jaimito 计算他可以如何安排这些 **N** 个石头，以确保在与 Jimena 对战时一定获胜。这样一来，他就能悠然应对，每天都有不同的策略而不怕母亲怀疑他的用心。

第一行包含一个整数 **T**，表示测试用例的数量（$1 \leq T \leq 10^4$）。接下来的 **T** 行中，每行有一个整数 **N**，表示 Jaimito 拥有的石头数量（$2 \leq N \leq 10^5$）。

对每个测试用例，输出一行，表示能保证 Jaimito 获胜的不同初始石堆分布方式的数量。由于结果可能非常大，输出时请取模 $10^9 + 7$。 **本翻译由 AI 自动生成**