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;
double f[202][256][2][244];
int x, k, p;
void upd(int i, int j, double v) {
  int a = j % 256;
  int x = j / 256;
  int b = x % 2;
  int c = 0;
  while (x && x % 2 == b) {
    ++c;
    x >>= 1;
  }
  f[i][a][b][c] += v;
}
void upd(int i, int a, int b, int c, double v) {
  if (a >= 256) {
    a %= 256;
    if (b) {
      b = 0;
    } else {
      if (c == 0) {
        b = c = 1;
      } else if (c == 1) {
        b = 1;
        c = 2;
      } else {
        b = c = 1;
      }
    }
  }
  f[i][a][b][c] += v;
}
void upd2(int i, int a, int b, int c, double v) {
  a <<= 1;
  int h = a / 256;
  a %= 256;
  if (h) {
    if (b) {
      ++c;
    } else {
      b = h;
      c = 1;
    }
  } else {
    if (b) {
      b = h;
      c = 1;
    } else {
      if (c) ++c;
    }
  }
  f[i][a][b][c] += v;
}
int calc(int a, int b, int c) {
  int res = 0;
  if (a == 0) {
    if (b) {
      res = 8;
    } else {
      if (c != 0) res = c + 8;
    }
  } else {
    while (a && a % 2 == 0) {
      a >>= 1;
      ++res;
    }
  }
  return res;
}
int main() {
  while (~scanf("%d%d%d", &x, &k, &p)) {
    memset(f, 0, sizeof(f));
    upd(0, x, 1);
    for (int i = (0); i < (k); i++) {
      for (int a = (0); a < (256); a++)
        for (int b = (0); b < (2); b++)
          for (int c = (0); c < (233); c++) {
            double v1 = f[i][a][b][c] * (100 - p) / 100;
            double v2 = f[i][a][b][c] * p / 100;
            upd(i + 1, a + 1, b, c, v1);
            upd2(i + 1, a, b, c, v2);
          }
    }
    double ans = 0;
    for (int a = (0); a < (256); a++)
      for (int b = (0); b < (2); b++)
        for (int c = (0); c < (233); c++) {
          double v = f[k][a][b][c];
          int t = calc(a, b, c);
          ans += v * t;
        }
    printf("%.13f\n", ans);
  }
  return 0;
}