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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class E {
    BufferedReader br;
    StringTokenizer in;
    PrintWriter out;

    public String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }
        return in.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public static void main(String[] args) throws IOException {
        new E().run();
    }

    public void solve() throws IOException {
        int x = nextInt();
        int k = nextInt();
        int p = nextInt();
        final int MAXJ = 230;
        double[][][][] dp = new double[2][2][MAXJ + 1][256];
        int ki = x % 256;
        int last;
        if (((x >> 8) & 1) == 0) {
            last = 0;
        } else {
            last = 1;
        }
        int i = 8;
        int cnt = 0;
        int qwe = x >> 8;
        while (qwe % 2 == last && cnt < MAXJ) {
            cnt++;
            i++;
            qwe /= 2;
        }
        dp[0][last][cnt][ki] = 1;
        for (i = 0; i < k; i++) {
            int cur = i % 2;
            int next = (i + 1) % 2;
            for (last = 0; last < 2; last++) {
                for (int j = 0; j <= MAXJ; j++) {
                    for (int l = 0; l < 256; l++) {
                        {
                            int newl = (l + 1) % 256;
                            int newj = j;
                            int newlast = last;
                            if (l == 255) {
                                if (last == 0) {
                                    newj = 1;
                                } else {
                                    newj = j;
                                }
                                newlast = 1 - last;
                            }
                            //out.println((i + 1) + " " + newlast + " " + newj + " " + newl);
                            //out.flush();
                            dp[next][newlast][newj][newl] += dp[cur][last][j][l] * (100 - p) / 100;
                        }
                        {
                            int newl = (l * 2) % 256;
                            int newj = j;
                            int newlast = l >> 7;
                            if (newlast == last) {
                                newj = Math.min(newj + 1, MAXJ);
                            } else {
                                newj = 1;
                            }
                            //out.println((i + 1) + " " + newlast + " " + newj + " " + newl);
                            //out.flush();
                            dp[next][newlast][newj][newl] += dp[cur][last][j][l] * p / 100;
                        }
                    }
                }
            }
            for (last = 0; last < 2; last++) {
                for (int j = 0; j <= MAXJ; j++) {
                    for (int l = 0; l < 256; l++) {
                        dp[cur][last][j][l] = 0;
                    }
                }
            }
        }
        i = k % 2;
        double res = 0;
        for (last = 0; last < 2; last++) {
            for (int j = 0; j <= MAXJ; j++) {
                for (int l = 0; l < 256; l++) {
                    if (dp[i][last][j][l] != 0.0) {
                        //out.println(last + " " + j + " " + l + " " + dp[i][last][j][l]);
                        int nulls = 0;
                        int ik = l;
                        while (ik % 2 == 0) {
                            nulls++;
                            ik /= 2;
                            if (nulls == 8) {
                                if (last == 0) {
                                    nulls += j;
                                }
                                break;
                            }
                        }
                        res += nulls * dp[i][last][j][l];
                    }
                }
            }
        }
        out.println(res);
    }

    public void run() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);

            solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
    }
}