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 long long LLINF = 1e18;
const int INF = 1e9;
const double EPS = 1e-7;
inline const int &INT() {
  static int x;
  scanf("%d", &x);
  return x;
}
inline const long long &LONG() {
  static long long x;
  scanf("%lld", &x);
  return x;
}
template <class T>
inline void MIN(T &a, const T &b) {
  if (b < a) a = b;
}
template <class T>
inline void MAX(T &a, const T &b) {
  if (b > a) a = b;
}
const int NN = 234, SS = 256;
int X, K, P;
double F[2][NN][SS], G[2][NN][SS];
int bit[33];
int main() {
  cin >> X >> K >> P;
  for (int t = 0; t < (2); ++t)
    for (int i = 0; i < (NN); ++i)
      for (int j = 0; j < (SS); ++j) F[t][i][j] = 0;
  for (int i = 0; i < (30); ++i) bit[i] = (X >> i) & 1;
  int p = 8;
  while (p < 30 && bit[p] == bit[8]) ++p;
  F[bit[8]][p - 8][X & (1 << 8) - 1] = 1;
  for (int zz = 0; zz < (K); ++zz) {
    for (int t = 0; t < (2); ++t)
      for (int i = 0; i < (NN); ++i)
        for (int j = 0; j < (SS); ++j) G[t][i][j] = 0;
    for (int t = 0; t < (2); ++t)
      for (int j = 0; j < (NN); ++j)
        for (int m = 0; m < (SS); ++m) {
          double tmp;
          tmp = F[t][j][m] * P / 100;
          int tt = ((m >> 7) & 1);
          int jj = (tt == t ? j + 1 : 1);
          int mm = (m << 1) & (1 << 8) - 1;
          if (jj >= NN) continue;
          G[tt][jj][mm] += tmp;
          tmp = F[t][j][m] * (100 - P) / 100;
          mm = (m + 1) & (1 << 8) - 1;
          if (mm) {
            tt = t;
            jj = j;
          } else {
            if (t == 1) {
              tt = 0;
              jj = j;
            } else {
              tt = 1;
              jj = 1;
            }
          }
          if (jj >= NN) continue;
          G[tt][jj][mm] += tmp;
        }
    for (int t = 0; t < (2); ++t)
      for (int i = 0; i < (NN); ++i)
        for (int j = 0; j < (SS); ++j) F[t][i][j] = G[t][i][j];
  }
  double ans = 0;
  for (int t = 0; t < (2); ++t)
    for (int i = 0; i < (NN); ++i)
      for (int j = 0; j < (SS); ++j) {
        int k = 0;
        while (k < 8 && (1 & (j >> k)) == 0) ++k;
        if (!j && !t) k += i;
        ans += F[t][i][j] * k;
      }
  printf("%.13lf\n", ans);
  return 0;
}