Continuing from the previous problem with young Kaito...
After using up all of his spare change yet failing to obtain every Gachapon toy in the set, Kaito sits at home in his room feeling disappointed. He is scrolling on his phone when he sees a new game available to download, which includes all the characters from his favorite show! After downloading the game, players can collect virtual "cards" which represent the major characters, but there also exist cards for every other character, location, item, and event, resulting in a very large quantity of available cards to collect.
In order to obtain a "card", the player spends 1 diamond of in-game currency to
flip a coin with 50:50 odds. If the result of that flip is "heads", then the player
receives one random "card" from the entire set.
The game sells its in-game currency at a rate of 1 diamond for X cents of real-world
money. Kaito realizes that his mother's credit card information is still tied to his phone,
and so he quickly downloads the game in an effort to collect at least one copy of each
virtual "card".
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each in the format N X, with N being the number of unique
items in the set, X the cost to perform one flip in cents.
Answer
Should consist of Q space-separated values, corresponding to the expected
value of cents to be 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.
That is, the result of one prize does not impact the result of any other
prize.
Round each result to the nearest integer, then report that rounded value modulo 1000000007.
Example
input data:
3
432 1
123 45
98765432 10
answer:
5743 59706 502170356