← 返回题目列表

AtCoder · dwacon2018_final_d

D. 与二王后君的游戏

中文机器翻译题面 查看原题

配点 : 1400 点

問題文

正在玩某个游戏。在这个游戏中,Q 由于敌人存在,需要巧妙操作玩家来击败敌人。此外,每个敌人 体力 被设定为一个值, 第i 个敌人的体力为 对于 niwan 哥操作的玩家 N_i 。

,魔力 被设定为一个值。 当遇到敌人时,玩家的魔力为 1 。 请注意,每次遇到敌人时,这个魔力会回到 1 。 Wango 哥每个回合可以执行以下操作之一。

  • 操作 1:将魔力增加 1 。
  • 操作 2:将当前魔力作为 x ,将魔力更改为 2x 。
  • 操作 3:将当前魔力作为 x ,将魔力更改为 2x + 1 。

当玩家的魔力刚好等于敌人的体力时,特殊的魔法会发动,可以击败敌人。 但是,如果魔力超过了敌人的体力,就无法再击败敌人。因此,不得进行会导致魔力超过敌人体力的操作。 玩家操作不会改变敌人的体力。

niwan哥想知道,击败敌人之前的操作方法有多少种。 对于每个敌人,请求出niwan哥击败敌人之前的操作方法有多少种 {\rm mod} 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 点。

入力

输入将以以下形式从标准输入给出。

Q
N_1
N_2
:
N_Q

出力

答案是 Q 行。i 行中,i 第几个敌人被击败之前的操作方法有多少种 {\rm mod} 1,000,000,007 输出。


入力例 1

1
4

出力例 1

5

1 个敌人的体力为 对于 niwan 哥操作的玩家 4 是。 要将魔力正好 4 调整到该数值的操作方法如下:按 5 有一条街。

  • 操作 1, 操作 1, 操作 1 顺序进行操作。
  • 操作 1, 操作 2 顺序进行操作。
  • 操作 2, 操作 1, 操作 1 顺序进行操作。
  • 操作 2, 操作 2 顺序进行操作。
  • 操作 3, 操作 1 顺序进行操作。

这里,无论先进行操作 1 ,还是进行操作 2 ,魔力变化的方式都不会改变,但请注意,这 2 个操作是区分开的。 对于第


入力例 2

2
2
1

出力例 2

2
1

1 个敌人,击败该敌人的操作方法有 2 种。 对于第

2 个敌人,即使完全不进行任何操作,最初玩家的魔力也已经等于敌人的体力。 这里需要注意,玩家的魔力在 2 第几个敌人遇到时会恢复到 1 的值。 不要忘记在


入力例 3

3
1000
2000
3000

出力例 3

415443858
630306535
766913460

{\rm mod} 1,000,000,007 输出。


入力例 4

10
983102606006243867
653718290103598600
364611268624595444
114746989192634390
81304291426411017
931878752092058491
395809284336497545
633900034071891379
895817108011279740
92661392530626177

出力例 4

893653300
150104699
232570112
922156483
361136690
103094234
245249617
912578727
399641917
820143308