Binary Frog

Many thanks to Clive Fraser for creating this curious puzzle!

Jeremy the frog likes travelling long distances in a sequence of one or more jumps. He can make jumps of 63 different lengths. These lengths are all powers of 2. Specifically, Jeremy can make jumps of any length in the set {1, 2, 4, 8, 16, 32, ..., 2^62}. In any sequence of jumps he begins with the longest jump in the sequence. Long jumps require a lot of energy so all subsequent jumps are less than or equal to the length of the previous jump in the sequence. This is true even for sequences where Jeremy begins with a small jump.

Consider an example where Jeremy's jump sequence has a total length of 11. There are 14 possible jump sequences which satisfy the rules above and have a total length of 11. These are listed below.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
2, 1, 1, 1, 1, 1, 1, 1, 1, 1
2, 2, 1, 1, 1, 1, 1, 1, 1
2, 2, 2, 1, 1, 1, 1, 1
2, 2, 2, 2, 1, 1, 1
2, 2, 2, 2, 2, 1
4, 1, 1, 1, 1, 1, 1, 1
4, 2, 1, 1, 1, 1, 1
4, 2, 2, 1, 1, 1
4, 2, 2, 2, 1
4, 4, 1, 1, 1
4, 4, 2, 1
8, 1, 1, 1
8, 2, 1

In this problem you will be given several distances, each corresponding to the total length of a jump sequence. For each distance you are asked to determine how many different jump sequences could give rise to it. The number of possible sequences rises rapidly as the total distance increases. For example a distance of 901 corresponds to 990388828 different jump sequences. For this reason you are asked to give your answer modulo 1000000007 (10^9 +7). All distances will be less than 2^63.

Input/Output description: The first line of the input data will contain a single integer N for the number of problems. N lines will follow. Each of these consists of a single integer D which is the total length of the jump sequence. In each case, find the number of different jump sequences which have this total length. Give your answer modulo 1000000007 and combine all answers into a single string, separated by single spaces.

Example:

input:
5
11
261
901
76486
13440462

answer:
14 748508 990388828 639488943 839288281