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;
const int MAX_K = 200;
const int MAX_L = 30 + MAX_K;
const int BITS = 1 << 8;
const int BMSK = BITS - 1;
double dp[MAX_K + 1][BITS][2][MAX_L];
int main() {
  int x, k, pi;
  scanf("%d%d%d", &x, &k, &pi);
  double p = pi / 100.0, q = 1.0 - p;
  int sbits = x & BMSK, sb = 0, sl = 0;
  x >>= 8;
  if (x > 0) {
    if (x & 1) {
      sb = 1;
      while (x > 0 && (x & 1)) x >>= 1, sl++;
    } else {
      while (x > 0 && !(x & 1)) x >>= 1, sl++;
    }
  }
  dp[0][sbits][sb][sl] = 1.0;
  for (int i = 0; i < k; i++)
    for (int bits = 0; bits < BITS; bits++)
      for (int b = 0; b < 2; b++)
        for (int l = 0; l < MAX_L; l++)
          if (dp[i][bits][b][l] > 0.0) {
            int bits0 = bits << 1;
            int b0, l0;
            if (bits0 < BITS) {
              b0 = 0;
              if (l == 0)
                l0 = 0;
              else if (b == 0)
                l0 = l + 1;
              else
                l0 = 1;
            } else {
              bits0 &= BMSK;
              b0 = 1;
              if (l == 0 || b == 0)
                l0 = 1;
              else
                l0 = l + 1;
            }
            dp[i + 1][bits0][b0][l0] += dp[i][bits][b][l] * p;
            int bits1 = bits + 1;
            int b1, l1;
            if (bits1 < BITS)
              b1 = b, l1 = l;
            else {
              bits1 &= BMSK;
              if (b == 0)
                b1 = 1, l1 = 1;
              else
                b1 = 0, l1 = l;
            }
            dp[i + 1][bits1][b1][l1] += dp[i][bits][b][l] * q;
          }
  double e = 0;
  for (int bits = 0; bits < BITS; bits++) {
    int zl = 0;
    if (bits == 0)
      zl = 8;
    else
      for (int bits0 = bits; bits0 > 0 && !(bits0 & 1); bits0 >>= 1, zl++)
        ;
    for (int b = 0; b < 2; b++)
      for (int l = 0; l < MAX_L; l++) {
        int zl0 = zl;
        if (zl == 8 && b == 0) zl0 += l;
        e += dp[k][bits][b][l] * zl0;
      }
  }
  printf("%.13lf\n", e);
  return 0;
}