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:
/**
 * Problem: 
 * Source: 
 * Link: 
 * 
 * @author Alexei Ostrovski
 */

import java.io.*;
import java.util.*;


public class LuckyProbabilitySolver {

	public static final boolean DEBUG = false;
	
	public static void main(String[] args) {
		//redirect input and output
		if (DEBUG)
		{
			try {
				System.setIn(new FileInputStream("input.txt"));
				//System.setOut(new PrintStream("input.txt"));
			} catch (IOException e) {
				//nothing
			}
		}
		Scanner sc = new Scanner(System.in);

		//read data
		int p_l = sc.nextInt(), p_r = sc.nextInt();
		int v_l = sc.nextInt(), v_r = sc.nextInt();
		int k = sc.nextInt();
			
		//solve
		int[] lucky = generateLucky(Math.min(p_l, v_l), Math.max(p_r, v_r));
		long res = 0;
		
		for (int i = 0; i < lucky.length; i++)
			if ((lucky[i] >= p_l) && (lucky[i] <= p_r))
			{			
				int v_lo = (i + k - 1 < lucky.length) ? lucky[i + k - 1] : (v_r + 1);
				v_lo = Math.max(v_lo, v_l);
				int v_hi = (i + k < lucky.length) ? (lucky[i + k] - 1) : v_r;
				v_hi = Math.min(v_hi, v_r);
			
				//System.out.println("[" + lucky[i] + ", " + lucky[i] + "] -> [" + v_lo + ", " + v_hi + "]");
						
				int v_lo_2 = (i - k >= 0) ? (lucky[i - k] + 1) : v_l;
				v_lo_2 = Math.max(v_lo_2, v_l);
				int v_hi_2 = (i - k + 1 >= 0) ? lucky[i - k + 1] : (v_l - 1);
				v_hi_2 = Math.min(v_hi_2, v_r);
			
				//System.out.println("[" + lucky[i] + ", " +lucky[i] + "] -> [" + v_lo_2 + ", " + v_hi_2 + "]");
				
				if (v_hi_2 < v_lo)
				{
					if (v_hi >= v_lo)
						res += (v_hi - v_lo + 1);
					if (v_hi_2 >= v_lo_2)
						res += (v_hi_2 - v_lo_2 + 1);
				} else { // intervals intersect
					if (v_hi >= v_lo_2)
						res += (v_hi - v_lo_2 + 1);
				}
			}
		//System.out.println(res);
		
		for (int i = 0; i <= lucky.length; i++)
		{
			int p_lo = (i == 0) ? p_l : (lucky[i - 1] + 1);
			p_lo = Math.max(p_lo, p_l);
			int p_hi = (i < lucky.length) ? (lucky[i] - 1) : p_r;
			p_hi = Math.min(p_hi, p_r);
			
			if (p_lo > p_hi)
				continue;
			
			int v_lo = (i + k - 1 < lucky.length) ? lucky[i + k - 1] : (v_r + 1);
			v_lo = Math.max(v_lo, v_l);
			int v_hi = (i + k < lucky.length) ? (lucky[i + k] - 1) : v_r;
			v_hi = Math.min(v_hi, v_r);
			
			//System.out.println("[" + p_lo + ", " + p_hi + "] -> [" + v_lo + ", " + v_hi + "]");
			
			if (v_lo <= v_hi)
				res += ((long) (p_hi - p_lo + 1)) * (v_hi - v_lo + 1);
			
			v_lo = (i - k - 1 >= 0) ? (lucky[i - k - 1] + 1) : v_l;
			v_lo = Math.max(v_lo, v_l);
			v_hi = (i - k >= 0) ? lucky[i - k] : (v_l - 1);
			v_hi = Math.min(v_hi, v_r);
			
			//System.out.println("[" + p_lo + ", " + p_hi + "] -> [" + v_lo + ", " + v_hi + "]");
			
			if (v_lo <= v_hi)
				res += ((long) (p_hi - p_lo + 1)) * (v_hi - v_lo + 1);
		}	
		//System.out.println(res);	
		
		//output
		long total = ((long) (p_r - p_l + 1)) * (v_r - v_l + 1);
		double result = ((double) res) / total; 
		System.out.format(Locale.ENGLISH, "%.12f\n", result);
		//slowSolution(p_l, p_r, v_l, v_r, k);
	}

	private static int[] generateLucky(int min, int max)
	{
		final int MAX = 3000;
		int[] store = new int[MAX];
		int count = 0;
		
		int maxDigits = 0;
		long pow = 1;
		while (pow < max)
		{
			maxDigits++;
			pow *= 10;
		}
		
		for (int digits = 1; digits <= maxDigits; digits++)
		{
			
			pow = 1;
			for (int i = 0; i < digits; i++)
				pow *= 2;
			
			for (int mask = 0; mask < pow; mask++)
			{
				int x = mask;
				long res = 0;
				
				for (int i = 0; i < digits; i++)
				{
					res += (x % 2 == 0) ? 4 : 7;
					x /= 2;
					res *= 10;
				}
				res /= 10;
				
				if ((res >= min) && (res <= max))
				{
					store[count] = (int) res;
					count++;
				}
			}
		}
		
		int[] result = new int[count];
		System.arraycopy(store, 0, result, 0, count);
		Arrays.sort(result);
		return result; 
	}
	
	private static double slowSolution(int p_l, int p_r, int v_l, int v_r, int k) {
		
		int[] lucky = generateLucky(Math.min(p_l, v_l), Math.max(p_r, v_r));
		long total = ((long) (p_r - p_l + 1)) * (v_r - v_l + 1);
		long res = 0;
		
		for (int p = p_l; p <= p_r; p++)
			for (int v = v_l; v <= v_r; v++)
			{
				int lo = Math.min(v, p), hi = Math.max(v, p);
				
				//if (Arrays.binarySearch(lucky, p) < 0)
				//	continue;
				
				int loIdx = Arrays.binarySearch(lucky, lo);
				if (loIdx < 0)
					loIdx = -loIdx - 1;
				int hiIdx = Arrays.binarySearch(lucky, hi);
				if (hiIdx < 0)
					hiIdx = -hiIdx - 2;
				if (hiIdx - loIdx + 1 == k)
					res++;
			}
		
		System.out.println(res + "/" + total);
		return 0;
	}
}