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.util.Scanner;

public class LuckyProbability
{
    static final int LIMIT = (int)Math.pow(10, 9);
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int pl = sc.nextInt();
        int pr = sc.nextInt();
        int vl = sc.nextInt();
        int vr = sc.nextInt();
        int k = sc.nextInt();
        
        int ln = 1 << 10;
        int[] lucky = new int[ln];
        int y = 0;
        for (int b = 1; b <= 9; ++b)
        {
            for (int i = 0; i < (1 << b); ++i)
            {
                String str = Integer.toBinaryString(i);
                for (int j = str.length(); j < b; ++j)
                {
                    str = "0" + str;
                }
                str = str.replace('0', '4');
                str = str.replace('1', '7');
                lucky[y++] = Integer.parseInt(str);
            }
        }
        
        int lmi = 0;
        int lmx = y - 1;
        int pvx = Math.max(pr, vr);
        int pvi = Math.min(pl, vl);
        for (int i = 0; i < y; ++i)
        {
            if (pvx < lucky[i])
            {
                lmx = i - 1;
                break;
            }
        }
        for (int i = y - 1; i >= 0; --i)
        {
            if (pvi > lucky[i])
            {
                lmi = i + 1;
                break;
            }
        }
        
        long n = 0;
        for (int li = lmi; li <= lmx; ++li)
        {
            int lx = li + k - 1;
            if (lx > lmx)
            {
                break;
            }
            
            int ai = 0;
            if (li > 0)
            {
                ai = lucky[li-1] + 1;
            }
            
            boolean b = pl > lucky[li] || pr < ai;
            int aip = Math.max(ai, pl);
            int ax = Math.min(lucky[li], pr);
            long pa = b ? 0 : ax - aip + 1;
            
            b = vl > lucky[li] || vr < ai;
            int aiv = Math.max(ai, vl);
            ax = Math.min(vr, lucky[li]);
            long va = b ? 0 : ax - aiv + 1;
            
            int bx = LIMIT;
            if (lx < y - 1)
            {
                bx = lucky[lx+1] - 1;
            }
            
            b = vl > bx || vr < lucky[lx];
            int bi = Math.max(lucky[lx], vl);
            int bxv = Math.min(bx, vr);
            long vb = b ? 0 : bxv - bi + 1;
            
            b = pl > bx || pr < lucky[lx];
            bi = Math.max(lucky[lx], pl);
            int bxp = Math.min(bx, pr);
            long pb = b ? 0 : bxp - bi + 1;
            
            n += (pa * vb + va * pb);
            
            if (ax == bi && ax == lucky[li] && pa * vb * va * pb != 0)
            {
                n--;
            }
        }
        
        long t = (long)(pr - pl + 1) * (long)(vr - vl + 1);
        double p = (n * 1.0) / t;
        System.out.println(p);
    }
}