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.