AT_dwacon2018_final_d ニワンゴくんとゲーム

dwango 公司的员工“ニワンゴくん”正在玩一个游戏。在这个游戏中，会出现 $Q$ 个敌人，玩家需要巧妙操作来击败这些敌人。每个敌人都有一个被称为**体力**的数值，第 $i$ 个敌人的体力为 $N_i$。 ニワンゴくん操作的玩家有一个被称为**魔力**的数值。每当遭遇敌人时，玩家的魔力为 $1$。需要注意的是，每当遭遇新敌人时，魔力都会重置为 $1$。ニワンゴくん每回合可以进行以下任意一种操作： - 操作 $1$：将魔力增加 $1$。 - 操作 $2$：假设当前魔力为 $x$，将魔力变为 $2x$。 - 操作 $3$：假设当前魔力为 $x$，将魔力变为 $2x+1$。 当玩家的魔力**恰好**等于敌人的体力时，会发动特殊魔法，敌人会被击败。需要注意：如果魔力超过了敌人的体力，则无法再击败该敌人，因此不能进行使魔力超过敌人体力的操作。玩家的操作不会影响敌人的体力。 ニワンゴくん很好奇，对于每个敌人，玩家有多少种不同的操作方法能够击败敌人。在这里，如果在任意一步选择的操作的编号不同，即便中间的魔力变化完全相同，也视为不同的操作方法。 请对于每个敌人，计算出将魔力提高到等于敌人体力的操作方法总数，结果对 $1\,000\,000\,007$ 取模。

输入为以下格式，从标准输入读取。 > $Q$ $N_1$ $N_2$ $:$ $N_Q$

请输出 $Q$ 行，第 $i$ 行输出能击败第 $i$ 个敌人的操作方法总数，对 $1\,000\,000\,007$ 取模。

## 限制条件 - $1 \leq Q \leq 200$ - $1 \leq N_i \leq 10^{18}$（$1 \leq i \leq Q$） - $N_i$ 是整数 ## 部分得分 - 若对于 $Q=1$ 且 $1 \leq N_1 \leq 10^{14}$ 的数据集能输出正确答案，将获得 $1300$ 分。 ## 样例解释 1 第 $1$ 个敌人的体力为 $4$。将魔力恰好提升到 $4$ 的操作方法有如下 $5$ 种： - 先执行操作 $1$，再操作 $1$，再操作 $1$。 - 先操作 $1$，再操作 $2$。 - 先操作 $2$，再操作 $1$，再操作 $1$。 - 先操作 $2$，再操作 $2$。 - 先操作 $3$，再操作 $1$。 需要注意，即使在第一步选择了操作 $1$ 或操作 $2$，魔力的变化可能一样，但因为操作编号不同，这两种操作方法是不同的。 ## 样例解释 2 对于第 $1$ 个敌人，有 $2$ 种方法可以击败。对于第 $2$ 个敌人，即使什么操作都不进行，一开始魔力即为敌人当前体力。需要注意的是，每次遇到新敌人，魔力都会重置为 $1$。 ## 样例解释 3 别忘了最后的结果要对 $1\,000\,000\,007$ 取模。 由 ChatGPT 5 翻译