Problem Description

Niwango-kun, an employee of dwango, is playing a certain game. In this game, $ Q $ enemies appear, and the player needs to skillfully operate the character to defeat them. Each enemy has a value called HP, and the HP of the $ i $th enemy is $ N_i $.

The player controlled by Niwango-kun has a value called magic power. When encountering an enemy, the player's magic power is $ 1 $. Note that the magic power resets to $ 1 $ each time an enemy is encountered. Niwango-kun can perform one of the following operations each turn:

• Operation $ 1 $: Increase magic power by $ 1 $.
• Operation $ 2 $: Change the current magic power $ x $ to $ 2x $.
• Operation $ 3 $: Change the current magic power $ x $ to $ 2x + 1 $.

When the player's magic power exactly matches the enemy's HP, a special spell is activated, allowing the player to defeat the enemy. However, if the magic power exceeds the enemy's HP, the enemy cannot be defeated. Therefore, operations that would cause the magic power to exceed the enemy's HP should not be performed. The enemy's HP does not change due to the player's operations.

Niwango-kun is curious about how many ways there are to defeat each enemy. For each enemy, find how many ways there are to defeat them until the magic power exactly matches their HP, modulo $ 1,000,000,007 $. Note that if the sequence of operations performed even once differs, it should be counted as a different way, even if the intermediate magic power values are the same.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ N_1 $ $ N_2 $ $ : $ $ N_Q $

Output Format

Output the answer in $ Q $ lines. The $ i $th line should contain the number of ways to defeat the $ i $th enemy modulo $ 1,000,000,007 $.

Sample Input and Output

Sample Input #1

1
4

Sample Output #1

5

Sample Input #2

2
2
1

Sample Output #2

2
1

Sample Input #3

3
1000
2000
3000

Sample Output #3

415443858
630306535
766913460

Sample Input #4

10
983102606006243867
653718290103598600
364611268624595444
114746989192634390
81304291426411017
931878752092058491
395809284336497545
633900034071891379
895817108011279740
92661392530626177

Sample Output #4

893653300
150104699
232570112
922156483
361136690
103094234
245249617
912578727
399641917
820143308

Notes/Hints

Constraints

• $1 \leq Q \leq 200$
• $1 \leq N_i \leq 10^{18}$ ($1 \leq i \leq Q$)
• $ N_i $ is an integer

Partial Points

• Correctly solving the dataset where $ Q = 1 $ and $1 \leq N_1 \leq 10^{14}$ will award $ 1300 $ points.

Sample Explanation 1

The HP of the first enemy is $ 4 $. There are $ 5 $ ways to reach exactly $ 4 $ magic power:
- Perform Operation $ 1 $, Operation $ 1 $, Operation $ 1 $ in that order.
- Perform Operation $ 1 $, Operation $ 2 $ in that order.
- Perform Operation $ 2 $, Operation $ 1 $, Operation $ 1 $ in that order.
- Perform Operation $ 2 $, Operation $ 2 $ in that order.
- Perform Operation $ 3 $, Operation $ 1 $ in that order.
Note that even if the way the magic power changes is the same, operations $ 1 $ and $ 2 $ are distinguished.

Sample Explanation 2

For the first enemy, there are $ 2 $ ways to defeat it. For the second enemy, no operations are needed as the player's magic power is already equal to the enemy's HP. Note that the player's magic power resets to $ 1 $ when encountering the second enemy.

Sample Explanation 3

Remember to output the answer modulo $ 1,000,000,007 $.

见题面 Input 部分

见题面 Output 部分