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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
long double dp[2][1 << 9 + 1][2][(400 + 20)];
int len[1 << 9];
int main() {
  int x, k, p;
  scanf("%d%d%d", &x, &k, &p);
  int mask = (1 << 9) - 1;
  if (x <= mask) {
    dp[0][x][0][200] = 1;
  } else {
    int b = (x >> 9) & 1;
    int cnt = 0;
    for (int i = 9; (1 << i) <= x; ++i) {
      if (((x >> i) & 1) == b)
        ++cnt;
      else
        break;
    }
    dp[0][x & mask][b][cnt] = 1;
  }
  int cur = 0, pre = 1;
  long double P = p / 100.0;
  for (int i = 0; i < k; ++i) {
    cur ^= 1, pre ^= 1;
    memset(dp[cur], 0, sizeof dp[cur]);
    for (int s = 0; s <= mask; ++s) {
      for (int b = 0; b < 2; ++b) {
        for (int cnt = 0; cnt < (400 + 20); ++cnt)
          if (dp[pre][s][b][cnt] != 0) {
            long double tmp = dp[pre][s][b][cnt];
            int ns = s + 1;
            if (ns == (1 << 9)) {
              ns = 0;
              if (b == 1)
                dp[cur][ns][b ^ 1][cnt] += tmp * (1 - P);
              else
                dp[cur][ns][1][1] += tmp * (1 - P);
            } else {
              dp[cur][ns][b][cnt] += tmp * (1 - P);
            }
            ns = s << 1;
            int ncnt = cnt;
            int nb = (ns >> 9) & 1;
            if (nb == b)
              ncnt++;
            else
              ncnt = 1;
            dp[cur][ns & mask][nb][ncnt] += tmp * P;
          }
      }
    }
  }
  for (int s = 0; s <= mask; ++s) {
    int c = 0;
    for (int i = 0; i < 9; ++i)
      if (s & (1 << i))
        break;
      else
        c++;
    len[s] = c;
  }
  double ans = 0;
  for (int s = 0; s <= mask; ++s) {
    for (int b = 0; b < 2; ++b) {
      for (int c = 0; c < (400 + 20); ++c)
        if (dp[cur][s][b][c] != 0) {
          if (s == 0) {
            if (b == 0)
              ans += dp[cur][s][b][c] * (c + 9);
            else
              ans += dp[cur][s][b][c] * 9;
          } else {
            ans += dp[cur][s][b][c] * len[s];
          }
        }
    }
  }
  printf("%.10lf\n", ans);
}