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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

/**
 * Author -
 * User: kansal
 * Date: 8/29/11
 * Time: 10:41 PM
 */
public class LuckyProbable {
    public static void main(String[] args) {
        reader = new BufferedReader(new InputStreamReader(System.in));

        generateLuckyNums();

        int p1 = nextInt(), p2 = nextInt(), v1 = nextInt(), v2 = nextInt(), k = nextInt();
        final int MAX = 1000000001;

        double res = 0.0;
        int n = luckyNums.size();
        for(int i = 0; i < n; ++i) {
            int j = i + k - 1;
            if (j >= n) {
                break;
            }

            int a1 = (i == 0 ? 0 : luckyNums.get(i - 1)) + 1;
            int a2 = luckyNums.get(i);
            int b1 = luckyNums.get(j);
            int b2 = (j == n-1 ? MAX : luckyNums.get(j + 1)) - 1;

            res += calc(a1, a2, b1, b2, p1, p2, v1, v2);
            res += calc(b1, b2, a1, a2, p1, p2, v1, v2);
        }

        if (k == 1) {
            int left = Math.max(p1, v1);
            int right = Math.min(p2, v2);
            int decrease = 0;
            for(int x: luckyNums) {
                if (x >= left) {
                    if (x > right) break;
                    ++decrease;
                }
            }
            res -= decrease;
        }
        double tot = 1.0 * (p2 - p1 + 1) * (v2 - v1 + 1);

        System.out.println(res/tot);
    }

    private static double calc(int a1, int a2, int b1, int b2, int p1, int p2, int v1, int v2) {
        double x = calc(a1, a2, p1, p2);
        double y = calc(b1, b2, v1, v2);
        return x * y;
    }

    private static double calc(int a1, int a2, int p1, int p2) {
        int x = Math.max(a1, p1);
        int y = Math.min(a2, p2);
        return Math.max(y - x + 1, 0);
    }

    private static ArrayList<Integer> luckyNums;

    private static void generateLuckyNums() {
        luckyNums = new ArrayList<Integer>();
        int[] digit = new int[]{4,7};

        for(int bitLen = 1; bitLen < 10; ++bitLen) {
            for(int b = 0; b < (1 << bitLen); ++b) {
                int n = 0;
                for(int i = 0; i < bitLen; ++i) {
                    n = n * 10 + digit[(b >> i) & 1];
                }
                luckyNums.add(n);
            }
        }

        Collections.sort(luckyNums);
    }

    public static BufferedReader reader;

    public static StringTokenizer tokenizer = null;

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

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

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

    static public String next() {
        return nextToken();
    }

    static public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

}