配点 : 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