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.InputStreamReader;
import java.text.DecimalFormat;
import java.util.StringTokenizer;


public class Main {
    
    static long num[] = new long[5000];
    static int N = 0;
    static long Min, Max;
    
    static String changeComma(String a) {
        String b = "";
        int L = a.length();
        
        for (int i=0;i<L;i++) {
            if (a.charAt(i) == ',') {
                b += '.';
            } else {
                b += a.charAt(i);
            }
        }
            
        return b;
    }
    
    static void generate(long soFar, int remNumOfDigits) {
        if (remNumOfDigits == 0) {
            
            if ((soFar >= Min)&&(soFar <= Max)) {
                num[N] = soFar;
                N++;
            }
            
            return;
        }
        
        generate(soFar*10+4, remNumOfDigits-1);
        generate(soFar*10+7, remNumOfDigits-1);
        
    }
    
    
    public static void main(String[] args) throws Exception {
        int i,j,k;
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long PL = Integer.parseInt(st.nextToken());
        long PR = Integer.parseInt(st.nextToken());
        
        long VL = Integer.parseInt(st.nextToken());
        long VR = Integer.parseInt(st.nextToken());
        
        int K = Integer.parseInt(st.nextToken());
        
        Min = Math.min(PL, VL);
        Max = Math.max(PR, VR);
        
        for (i=1;i<=9;i++)
            generate(0, i);
        
        /*
        for (i=0;i<N;i++) {
            System.out.println(i+" "+num[i]);
        }
        */
        
        double prob = 0.0;
        
        long lEmpty, rEmpty;
        double a,b,c,d;
        long taken;
        
        for (i=0;i<N;i++) {
            
            j = i+K-1;
            
            if (j < N) {
                
                lEmpty = Min;
                rEmpty = Max;
                
                if (i-1 >= 0) {
                    lEmpty = num[i-1]+1;
                }
                
                if (j+1 <= N-1) {
                    rEmpty = num[j+1]-1;
                }
                
                // [lEmpty, num[i]]     [num[j], rEmpty]
                
                a = 0.0;
                
                if ((PL <= num[i])&&(PR >= lEmpty)) {
                    taken = 0;
                    if (PL < lEmpty) {
                        taken += (lEmpty-PL);
                    }
                    if (PR > num[i]) {
                        taken += (PR-num[i]);
                    }
                    a = ((double)(PR-PL+1-taken))/((double)(PR-PL+1));
                }
                
                b = 0.0;
                
                if ((PL <= rEmpty)&&(PR >= num[j])) {
                    taken = 0;
                    if (PL < num[j]) {
                        taken += (num[j]-PL);
                    }
                    if (PR > rEmpty) {
                        taken += (PR-rEmpty);
                    }
                    b = ((double)(PR-PL+1-taken))/((double)(PR-PL+1));
                }
                
                c = 0.0;
                
                if ((VL <= num[i])&&(VR >= lEmpty)) {
                    taken = 0;
                    if (VL < lEmpty) {
                        taken += (lEmpty-VL);
                    }
                    if (VR > num[i]) {
                        taken += (VR-num[i]);
                    }
                    c = ((double)(VR-VL+1-taken))/((double)(VR-VL+1));
                }
                
                d = 0.0;
                
                if ((VL <= rEmpty)&&(VR >= num[j])) {
                    taken = 0;
                    if (VL < num[j]) {
                        taken += (num[j]-VL);
                    }
                    if (VR > rEmpty) {
                        taken += (VR-rEmpty);
                    }
                    d = ((double)(VR-VL+1-taken))/((double)(VR-VL+1));
                }
                
                prob += a*d+b*c;
                
                
                if (K == 1) {
                    // special case
                    if ((PL <= num[i])&&(num[i] <= PR)&&(VL <= num[i])&&(num[i] <= VR)) {
                        prob -= (1.0/(((double)(PR-PL+1))*((double)(VR-VL+1))));
                    }
                }
                
                
            }
            
        }
        
        DecimalFormat df = new DecimalFormat("0.000000000000000000");
        System.out.println(changeComma(df.format(prob)));
        
    }

}