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:
//package codeforces;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

public class E {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(System.out);
    StringTokenizer stringTokenizer;

    String next() throws IOException {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

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

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

    @SuppressWarnings("unchecked")
    void solve() throws IOException {
        int x = nextInt();
        int k = nextInt();
        double p = 0.01 * nextInt();
        double ans = solve(x, k, p);
        writer.printf(Locale.US, "%.10f\n", ans);
        writer.close();
    }

    private double solve(int x, final int k, double p) {
        double q = 1.0 - p;
        class SmartNumber {
            int shift;
            int r;
            final int CAP = 1 << 8;

            SmartNumber(int x) {
                int y = x + k;
                y ^= x;
                y = Integer.highestOneBit(y);
                shift = Math.max(Integer.numberOfTrailingZeros(y), Integer.numberOfTrailingZeros(x));
                x &= (1 << shift + 1) - 1;
                r = x - (1 << shift);
            }

            SmartNumber(int shift, int r) {
                if(r > 0) {
                    shift = 0;
                }
                if(r < -k) {
                    shift = 0;
                    if(r == -CAP) {
                        shift = Integer.numberOfTrailingZeros(CAP);
                        r = 0;
                    }
                    r &= CAP - 1;
                }
                if(r > CAP) {
                    if(r % CAP == 0) {
                        shift = Integer.numberOfTrailingZeros(r);
                        r = 0;
                    } else {
                        int x = r;
                        int y = x + k;
                        y ^= x;
                        y = Integer.highestOneBit(y);
                        shift = Math.max(Integer.numberOfTrailingZeros(y), Integer.numberOfTrailingZeros(x));
                        x &= (1 << shift + 1) - 1;
                        r = x - (1 << shift);
                    }
                }
                this.shift = shift;
                this.r = r;
            }

            SmartNumber inc() {
                return new SmartNumber(shift, r + 1);
            }

            SmartNumber shift() {
                return new SmartNumber(shift + 1, r * 2);
            }

            int zeroes() {
                if(r == 0) return shift;
                return Integer.numberOfTrailingZeros(r);
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;

                SmartNumber that = (SmartNumber) o;

                if (r != that.r) return false;
                if (shift != that.shift) return false;

                return true;
            }

            @Override
            public int hashCode() {
                int result = shift;
                result = 31 * result + r;
                return result;
            }

            @Override
            public String toString() {
                return "SmartNumber{" +
                        "shift=" + shift +
                        ", r=" + r +
                        '}';
            }
        }
        class DebugSmartNumber extends SmartNumber {
            DebugSmartNumber parent;
            long x;
            DebugSmartNumber(int x) {
                super(x);
                this.x = x;
            }

            DebugSmartNumber(int shift, int r) {
                super(shift, r);
            }

            @Override
            SmartNumber inc() {
                DebugSmartNumber dsm = new DebugSmartNumber(shift, r + 1);
                dsm.x = x + 1;
                dsm.parent = this;
                dsm.check();
                return dsm;
            }

            @Override
            SmartNumber shift() {
                DebugSmartNumber dsm = new DebugSmartNumber(shift + 1, r * 2);
                dsm.x = x * 2;
                dsm.parent = this;
                dsm.check();
                return dsm;
            }

            void print() {
                if(parent != null) {
                    parent.print();
                }
                System.out.println(toString());
            }

            @Override
            public String toString() {
                return "DebugSmartNumber{" +
                        "x=" + x + ", " + Long.toBinaryString(x) +
                        "} " + super.toString();
            }

            void check() {
                if(zeroes() != Long.numberOfTrailingZeros(x)) {
                    print();
                    throw new RuntimeException("encoding sucks");
                }
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                if (!super.equals(o)) return false;

                DebugSmartNumber that = (DebugSmartNumber) o;

                if (x != that.x) return false;

                return true;
            }

            @Override
            public int hashCode() {
                int result = super.hashCode();
                result = 31 * result + (int) (x ^ (x >>> 32));
                return result;
            }
        }
        List<Map<SmartNumber, Double>> dp = new ArrayList<>(k + 1);
        for(int i = 0; i <= k; i++) {
            dp.add(new HashMap<SmartNumber, Double>());
        }
        dp.get(0).put(new SmartNumber(x), 1.0);
        for(int i = 0; i < k; i++) {
//            System.out.println(i + " " + dp.get(i).size());
            for (Map.Entry<SmartNumber, Double> entry : dp.get(i).entrySet()) {
                increment(dp.get(i + 1), entry.getKey().shift(), p * entry.getValue());
                increment(dp.get(i + 1), entry.getKey().inc(), q * entry.getValue());
            }
            dp.get(i).clear();
        }
        double ans = 0;
        for (Map.Entry<SmartNumber, Double> entry : dp.get(k).entrySet()) {
            ans += entry.getKey().zeroes() * entry.getValue();
        }
        return ans;
    }

    <K> void increment(Map<K, Double> map, K key, double value) {
        value += map.containsKey(key) ? map.get(key) : 0;
        map.put(key, value);
    }

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