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 i, j, k, N, M, K, x;
long double dp[2][(1 << 9)][2][405], p, dv, ans;
int spmask = (1 << 8) - 1, mask, cnt, last, nmask, ncnt, nlast, ni;
int main() {
  memset(dp, 0, sizeof(dp));
  ans = 0;
  cnt = last = mask = 0;
  cin >> x >> k >> p;
  p /= 100;
  mask = x & (spmask);
  N = x >> 8;
  M = N % 2;
  while (N % 2 == M && N != 0) {
    cnt++;
    N /= 2;
  }
  cout << fixed << setprecision(10);
  dp[0][mask][M][cnt] = 1.0;
  int c;
  for (c = 0; c <= k; c++) {
    i = c % 2;
    for (mask = 0; mask <= (1 << 8) - 1; mask++) {
      for (last = 0; last <= 1; last++) {
        for (cnt = 0; cnt <= 400; cnt++) {
          dp[i ^ 1][mask][last][cnt] = 0;
        }
      }
    }
    for (mask = 0; mask <= (1 << 8) - 1; mask++) {
      for (last = 0; last <= 1; last++) {
        for (cnt = 0; cnt <= 400; cnt++) {
          dv = dp[i][mask][last][cnt];
          ni = (i + 1) % 2, nmask = (mask + 1) & spmask;
          if (nmask == 0) {
            if (last == 0) {
              nlast = 1, ncnt = 1;
            } else {
              ncnt = cnt, nlast = 0;
            }
          } else {
            nlast = last, ncnt = cnt;
          }
          dp[ni][nmask][nlast][ncnt] += (1 - p) * dv;
          ni = (i + 1) % 2, nmask = (mask << 1) & spmask,
          nlast = ((1 << 7) & mask) > 0;
          if (last == nlast) {
            ncnt = cnt + 1;
          } else {
            ncnt = 1;
          }
          dp[ni][nmask][nlast][ncnt] += p * dv;
          if (i == 0 && mask == 255 && last == 0 && cnt == 0) {
          }
        }
      }
    }
  }
  for (c = k; c <= k; c++) {
    int i = c % 2;
    for (mask = 0; mask <= (1 << 8) - 1; mask++) {
      for (last = 0; last <= 1; last++) {
        for (cnt = 0; cnt <= 400; cnt++) {
          int ret = 0;
          if (mask == 0) {
            ret = 8;
            if (last == 0) {
              ret += cnt;
            }
          } else {
            N = mask;
            while (N != 0 && N % 2 == 0) ret++, N /= 2;
          }
          ans += ret * dp[i][mask][last][cnt];
        }
      }
    }
  }
  cout << ans << endl;
}