Infinite Cash

Time limit1sMemory limit1024 MB

Summary

Given a salary s, a pay interval d, and starting cash m, all in binary up to 2^1000, find the first day Svalur has no money to spend, or report infinite money.

Level: Medium6 of 10
Topics: Math, Bit manipulation
Solved: No attempts yet

Problem

Svalur Handsome has finally graduated with a degree in computer science. He has some rather unwise spending habits, and he hopes a high paying job as a programmer will make them more sustainable. He has applied to a few places, and now has a contract in his hands that he could sign and start working on almost immediately. 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$ -th day. He currently has $m$ ISK to spend as well.

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.

Output

Print the number of the day on which Svalur wants to spend money but has none. This number must also be printed in binary. If he can support his spending habits indefinitely, print Infinite money! instead.

Examples3

Example 1
Input
```
101110101
1010
10001110101010101
```
Expected output
```
10011
```

Example 2

Input

101110101
1000
100011101

Expected output

Infinite money!

Example 3
Input
```
101110101
1010
100011101
```
Expected output
```
1001
```