Problem: Miki is a high school student. She has a part time job, so she cannot take enough sleep on weekdays. She wants to take good sleep on holidays, but she doesn't know the best length of sleeping time for her. She is now trying to figure that out with the following algorithm:

1. Begin with the numbers K, R and L.
2. She tries to sleep for H=(R+L)/2 hours.
3. If she feels the time is longer than or equal to the optimal length, then update L with H. Otherwise, update R with H.
4. After repeating step 2 and 3 for K nights, she decides her optimal sleeping time to be T' = (R+L)/2.



If her feeling is always correct, the steps described above should give her a very accurate optimal sleeping time. But unfortunately, she makes mistake in step 3 with the probability P.

Assume you know the optimal sleeping time T for Miki. You have to calculate the probability PP that the absolute difference of T' and T is smaller or equal to E. It is guaranteed that the answer remains unaffected by the change of E in 10^{-10}.



Input

The input follows the format shown below

K R L
P
E
T


Where the integers 0 \leq K \leq 30, 0 \leq R \leq L \leq 12 are the parameters for the algorithm described above. The decimal numbers on the following three lines of the input gives the parameters for the estimation. You can assume 0 \leq P \leq 1, 0 \leq E \leq 12, 0 \leq T \leq 12.

Output

Output PP in one line. The output should not contain an error greater than 10^{-5}.

Examples

Input

3 0 2
0.10000000000
0.50000000000
1.00000000000


Output

0.900000


Input

3 0 2
0.10000000000
0.37499999977
1.00000000000


Output

0.810000


Input

3 0 2
0.10000000000
0.00000100000
0.37500000000


Output

0.729000


Input

3 0 2
0.20000000000
0.00000100000
0.37500000000


Output

0.512000

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;

public class Main {

    static int K, LO, HI;
    static double P, E, T;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        K = sc.nextInt();
        LO = sc.nextInt();
        HI = sc.nextInt();
        P = Double.parseDouble(sc.next());
        E = Double.parseDouble(sc.next());
        T = Double.parseDouble(sc.next());

        System.out.println(BigDecimal.valueOf(solve()).toPlainString());
    }

    static double EPS = 1e-11;

    static double solve() {
        return dfs(0, LO, HI, 1.0);
    }

    static double dfs(int k, double lo, double hi, double p) {
        double mid = (lo + hi)/2;
        if( k == K ) {
            if( Math.abs(T-mid) < E ) {
                return p;
            } else {
                return 0.0;
            }
        }

        // Kが最大30なので枝狩りしないと死ぬ
        // 含まれる -> p
        // 含まれない -> 0.0
        // lo hi T-E T
        if( hi < T-E ) return 0.0;
        // T T+E lo hi
        if( T+E < lo ) return 0.0;
        // T-E lo hi T+E
        if( T-E < lo && hi < T+E ) return p;

        if( T < mid ) {
            return dfs(k+1, lo, mid, p*(1-P)) + dfs(k+1, mid, hi, p*P);

        } else {
            return dfs(k+1, lo, mid, p*P) + dfs(k+1, mid, hi, p*(1-P));
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

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

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static void writeSingleLine(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < as.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(as[i]);
        }
        pw.println();
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg == null) j.add("null");
            else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }

    static void printSingleLine(int[] array) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < array.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(array[i]);
        }
        pw.println();
        pw.flush();
    }

    static int lowerBound(int[] array, int value) {
        int lo = 0, hi = array.length, mid;
        while (lo < hi) {
            mid = (hi + lo) / 2;
            if (array[mid] < value) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int upperBound(int[] array, int value) {
        int lo = 0, hi = array.length, mid;
        while (lo < hi) {
            mid = (hi + lo) / 2;
            if (array[mid] <= value) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}