Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

E. Valera and Number

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputValera is a coder. Recently he wrote a funny program. The pseudo code for this program is given below:

//input: integers x, k, p

a = x;

for(step = 1; step <= k; step = step + 1){

rnd = [random integer from 1 to 100];

if(rnd <= p)

a = a * 2;

else

a = a + 1;

}

s = 0;

while(remainder after dividing a by 2 equals 0){

a = a / 2;

s = s + 1;

}

Now Valera wonders: given the values *x*, *k* and *p*, what is the expected value of the resulting number *s*?

Input

The first line of the input contains three integers *x*, *k*, *p* (1 ≤ *x* ≤ 10^{9}; 1 ≤ *k* ≤ 200; 0 ≤ *p* ≤ 100).

Output

Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.

Examples

Input

1 1 50

Output

1.0000000000000

Input

5 3 0

Output

3.0000000000000

Input

5 3 25

Output

1.9218750000000

Note

If the concept of expected value is new to you, you can read about it by the link:

http://en.wikipedia.org/wiki/Expected_value

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 01:01:33 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|