Each of n days you independently choose option A with probability p and option B otherwise. Return the probability of choosing A on at least k consecutive days at some point.

Same shape as the coin-run problem, but the two outcomes are no longer equally likely and only a run of A counts.

Input

n = 10
k = 3
p = 0.5

Output

0.5078125