Problem: Valera 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 ≤ 109; 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int reader_pt = 1048576, reader_last;
char reader_buf[1048576];
void reader(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    {
      if (reader_pt == 1048576)
        reader_pt = 0,
        reader_last = fread(reader_buf, sizeof(char), 1048576, stdin);
      (k) = reader_buf[reader_pt++];
    };
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    {
      if (reader_pt == 1048576)
        reader_pt = 0,
        reader_last = fread(reader_buf, sizeof(char), 1048576, stdin);
      (k) = reader_buf[reader_pt++];
    };
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
void reader(int *x, int *y, int *z) {
  reader(x);
  reader(y);
  reader(z);
}
int X, K, P_;
double P;
int val[1024 + 1];
double dp[1024][1024], nx[1024][1024];
int main() {
  int i, j, k;
  double res;
  for (i = 1; i < 1024 + 1; i++) {
    j = i;
    k = 0;
    while (j % 2 == 0) k++, j /= 2;
    val[i] = k;
  }
  reader(&X, &K, &P_);
  P = P_ / 100.0;
  for (i = 0; i < 1024; i++)
    for (j = 0; j < 1024; j++) dp[i][j] = 0;
  if (X % 1024 == 0) {
    k = 0;
    while (X % 2 == 0) X /= 2, k++;
    dp[k][0] = 1;
  } else {
    k = X % 1024;
    X /= 1024;
    j = 0;
    while (X % 2 == 1) j++, X /= 2;
    dp[j][k] = 1;
  }
  while (K--) {
    for (i = 0; i < 1024; i++)
      for (j = 0; j < 1024; j++) nx[i][j] = 0;
    for (i = 0; i < 1024; i++)
      for (j = 0; j < 1024; j++)
        if (dp[i][j]) {
          if (j == 0) {
            nx[i + 1][j] += dp[i][j] * P;
            nx[0][1] += dp[i][j] * (1 - P);
            continue;
          }
          if (j * 2 > 1024)
            nx[i + 1][j * 2 % 1024] += dp[i][j] * P;
          else if (j * 2 == 1024)
            nx[val[1024]][0] += dp[i][j] * P;
          else
            nx[0][j * 2] += dp[i][j] * P;
          if (j != 1024 - 1)
            nx[i][j + 1] += dp[i][j] * (1 - P);
          else
            nx[val[1024] + i][0] += dp[i][j] * (1 - P);
        }
    for (i = 0; i < 1024; i++)
      for (j = 0; j < 1024; j++) dp[i][j] = nx[i][j];
  }
  res = 0;
  for (i = 0; i < 1024; i++)
    for (j = 0; j < 1024; j++)
      if (dp[i][j]) {
        if (j == 0)
          k = i;
        else
          k = val[j];
        res += dp[i][j] * k;
      }
  printf("%.9f\n", res);
  return 0;
}