Continuing from the previous problem with young Kaito...
After collecting every card in the mobile game he downloaded (having spent
a small fortune and getting in trouble with his mother in the process), Kaito now sits at home
watching television. Suddenly an advertisement appears for an update to the mobile game,
which adds a truly unfathomable amount of new cards! The previous update included up to
10 billion cards, but there are so many cards now that Kaito has difficulty visualizing
such massive numbers.
And the best part is - coin flips are now free! Well, players can now flip the coin for free only once per hour, but since his mother disconnected her credit card from his cell phone this will be Kaito's only option. Quickly he finds his phone, downloads the update, and starts the long process of collecting every card without spending any money.
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow wach with a single integer N being the number of unique
items in the set.
Answer
Should consist of Q space-separated values, corresponding to the expected
value of hours spent before receiving at least one of each type of item.
Assume that each type of item has an equal chance of being given each time.
Round each result to the nearest integer, then report that rounded value modulo 1000000007.
Example
input data:
2
123456789
999999999999999
answer:
371434216 814000561