Limak is in a casino.
He has **a** dollars.
He wants to have at least **b** dollars (to be able to buy a Valentine's day present for a girl he likes).
He will try to win the missing money by playing games in the casino.
He has enough time to play at most **k** times.
Limak is a simple bear, so he only plays the simplest game.
In this game he can bet any non-negative integer amount (not exceeding his current balance).
With probability 50% he loses the bet and with probability 50% he gets it back doubled.
For example, suppose he has 10 dollars and he bets 3. If he loses, he will have 10-3 = 7 dollars, if he wins, he will have 7+2*3 = 10+3 = 13 dollars.
Limak does not know anything about strategies.
Therefore, each time he plays a game, he chooses the amount to bet uniformly at random among all valid bets.
For example, if he currently has 5 dollars, in the next game he will bet 0, 1, 2, 3, 4, or 5 dollars, each with probability 1/6.
As soon as he has at least **b** dollars, he stops playing and leaves the casino.
He also leaves the casino after playing **k** games, regardless of whether he has reached his goal.
Of course, there are different ways to play this sequence of games.
An optimal strategy is a strategy that always chooses the amount one should bet in a way that maximizes the probability of reaching Limak's goal.
There can be multiple optimal strategies.
You are given the ints **a**, **b**, and **k**.
Compute the probability that the sequence of Limak's bets will follow an optimal strategy.
In other words, compute the probability that to a random observer (who knows Limak's goal but not his way of playing) it will seem that Limak follows an optimal strategy throughout his entire stay in the casino. |