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 inf = 987654321;
const long long int INF = 123456789987654321;
FILE *fin, *fout;
int X, K, P;
vector<vector<vector<double> > > cache;
double dp(int one_cnt, int cur_val, int turn) {
  double& ret = cache[one_cnt][cur_val][turn];
  if (ret != -1.0) return ret;
  if (turn == 0) {
    if (cur_val == 0)
      return ret = 8 + one_cnt;
    else {
      int zero_cnt = 0;
      while (cur_val % 2 == 0) {
        cur_val /= 2;
        zero_cnt++;
      }
      return ret = zero_cnt;
    }
  }
  if (cur_val == 0) {
    ret = 0;
    ret += (double)P / 100 * dp(one_cnt + 1, 0, turn - 1);
    ret += (double)(100 - P) / 100 * dp(0, 1, turn - 1);
    return ret;
  } else {
    ret = 0;
    if (1) {
      if (cur_val == (1 << 7))
        ret += (double)P / 100 * dp(0, 0, turn - 1);
      else if ((cur_val >> 7) & 1)
        ret += (double)P / 100 *
               dp(one_cnt + 1, (cur_val * 2) % (1 << 8), turn - 1);
      else
        ret += (double)P / 100 * dp(0, (cur_val * 2) % (1 << 8), turn - 1);
    }
    if (2) {
      if (cur_val == (1 << 8) - 1)
        ret += (double)(100 - P) / 100 * dp(one_cnt, 0, turn - 1);
      else
        ret += (double)(100 - P) / 100 * dp(one_cnt, cur_val + 1, turn - 1);
    }
    return ret;
  }
}
int main() {
  scanf("%d %d %d", &X, &K, &P);
  cache = vector<vector<vector<double> > >(
      240, vector<vector<double> >((1 << 8), vector<double>(K + 1, -1.0)));
  if (X % (1 << 8) == 0) {
    X /= (1 << 8);
    int zero_cnt = 0;
    while (X % 2 == 0) {
      X /= 2;
      zero_cnt++;
    }
    printf("%.20lf", dp(zero_cnt, 0, K));
  } else {
    int tmp = X % (1 << 8);
    X /= (1 << 8);
    int one_cnt = 0;
    while (X % 2 == 1) {
      X /= 2;
      one_cnt++;
    }
    printf("%.20lf", dp(one_cnt, tmp, K));
  }
}