Problem: Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya and his friend Vasya play an interesting game. Petya randomly chooses an integer p from the interval [pl, pr] and Vasya chooses an integer v from the interval [vl, vr] (also randomly). Both players choose their integers equiprobably. Find the probability that the interval [min(v, p), max(v, p)] contains exactly k lucky numbers.

Input

The single line contains five integers pl, pr, vl, vr and k (1 ≤ pl ≤ pr ≤ 109, 1 ≤ vl ≤ vr ≤ 109, 1 ≤ k ≤ 1000).

Output

On the single line print the result with an absolute error of no more than 10 - 9.

Examples

Input

1 10 1 10 2


Output

0.320000000000


Input

5 6 8 10 1


Output

1.000000000000

Note

Consider that [a, b] denotes an interval of integers; this interval includes the boundaries. That is, <image>

In first case there are 32 suitable pairs: (1, 7), (1, 8), (1, 9), (1, 10), (2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10), (4, 7), (4, 8), (4, 9), (4, 10), (7, 1), (7, 2), (7, 3), (7, 4), (8, 1), (8, 2), (8, 3), (8, 4), (9, 1), (9, 2), (9, 3), (9, 4), (10, 1), (10, 2), (10, 3), (10, 4). Total number of possible pairs is 10·10 = 100, so answer is 32 / 100.

In second case Petya always get number less than Vasya and the only lucky 7 is between this numbers, so there will be always 1 lucky number.

Solution (in JAVA):

Solution:

import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author pttrung
 */
public class B {

    public static void main(String[] args) {
        Scanner in = new Scanner(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        long pl = in.nextInt();
        long pr = in.nextInt();
        long vl = in.nextInt();
        long vr = in.nextInt();
        int k = in.nextInt();
        ArrayList<Long> list = new ArrayList();
        ArrayList<Long> hold = new ArrayList();
        hold.add((long) 0);
        while (list.size() < 1 << 10) {
            ArrayList<Long> temp = new ArrayList();
            while (!hold.isEmpty()) {
                long val = hold.remove(0);
                list.add(val * 10 + 4);
                list.add(val * 10 + 7);
                temp.add(val * 10 + 4);
                temp.add(val * 10 + 7);
            }
            hold = temp;
        }

        long count = 0;
        int length = list.size();
        //  System.out.println(list.get(length - 1));
        for (int i = 0; i < list.size() - k + 1; i++) {

            long val = list.get(i);
            long other = list.get(i + k - 1);
            long a = i > 0 ? list.get(i - 1) + 1 : 0;
            long b = i + k < list.size() ? list.get(i + k) - 1 : list.get(length - 1);
            //   System.out.println(a + " " + val + " " + b + " " + other);
            //   System.out.println(a + " " + b + " " + c + " " + d);
            if (isCut(pl, pr, a, val) && isCut(vl, vr, other, b)) {
                long total = (Math.min(pr, val) - Math.max(a, pl) + 1) * (Math.min(vr, b) - Math.max(other, vl) + 1);
                count += total;

            }
            if (isCut(pl, pr, other, b) && isCut(vl, vr, a, val)) {
                long total = (Math.min(vr, val) - Math.max(a, vl) + 1) * (Math.min(pr, b) - Math.max(other, pl) + 1);
                count += total;
            }

            if (isCut(pl, pr, vl, vr) && k == 1) {
                long c = Math.max(pl, vl);
                long d = Math.min(pr, vr);
                if (isCut(c, d, val, val) ) {                    
                    count -= 1;
                }
            }

        }
        //   System.out.println(count);
        long total = (pr - pl + 1) * (vr - vl + 1);
        //  System.out.println(total);
        out.println((double) count / total);

        out.close();
    }

    public static boolean isCut(long a, long b, long c, long d) {
        if (a <= c && b >= c) {
            return true;
        }
        if (a <= d && b >= d) {
            return true;
        }
        if (c <= a && d >= a) {
            return true;
        }
        if (c <= b && d >= b) {
            return true;
        }
        return false;
    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static class Point {

        int x, y, z;

        public Point(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    public double pow(double a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        double val = pow(a, b / 2);
        if (b % 2 == 0) {
            return val * val;
        } else {
            return val * val * a;
        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
}