Flip a fair coin n times. Return the probability of seeing at least one run of k identical outcomes in a row, heads or tails.

Count the sequences that never manage such a run and subtract. Track how long the current run is as you extend the sequence one flip at a time: each new flip either continues the run or starts a fresh one of length 1.

Input

n = 10
k = 3

Output

0.826171875