Problem I
Infinite Cash
Languages
en
is
Svalur Handsome has finally graduated with a degree in computer science, and it couldn’t have happened sooner. He has some rather unwise spending habits which he hopes will be more sustainable now that he can get a high paying job as a programmer. He has applied to a few places, and now has a contract in his hands that he could sign and start working almost immediately. But before he takes the offer he wants to figure out how long it could support his spending habits.
At the start of every day Svalur spends half of his remaining money, rounded up. The new job would pay $s$ ISK at the end of every $d$-th day, starting with the $(d-1)$-st day. He currently has $m$ ISK to spend as well. The days are zero indexed.
Input
The input has three lines, each containing the positive integers $s, d, m$ respectively. They satisfy $1 \leq s, d, m \leq 2^{1000}$. As these payment details are for a computer science job the numbers are all given in binary, naturally.
Output
Print the number of the day that Svalur wants to spend money, but has none. This should naturally also be printed in binary. If he can support his spending habits indefinitely instead print Infinite money!.
| Sample Input 1 | Sample Output 1 |
|---|---|
101110101 1010 10001110101010101 |
10011 |
| Sample Input 2 | Sample Output 2 |
|---|---|
101110101 1000 100011101 |
Infinite money! |
| Sample Input 3 | Sample Output 3 |
|---|---|
101110101 1010 100011101 |
1001 |
