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.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class CodeG 
{
	static class Scanner
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		
		public String nextLine()
		{
			try
			{
				return br.readLine();
			}
			catch(Exception e)
			{
				throw(new RuntimeException());
			}
		}
		
		public String next()
		{
			while(!st.hasMoreTokens())
			{
				String l = nextLine();
				if(l == null)
					return null;
				st = new StringTokenizer(l);
			}
			return st.nextToken();
		}
		
		public int nextInt()
		{
			return Integer.parseInt(next());
		}
		
		public long nextLong()
		{
			return Long.parseLong(next());
		}
		
		public double nextDouble()
		{
			return Double.parseDouble(next());
		}
		
		public int[] nextIntArray(int n)
		{
			int[] res = new int[n];
			for(int i = 0; i < res.length; i++)
				res[i] = nextInt();
			return res;
		}
		
		public long[] nextLongArray(int n)
		{
			long[] res = new long[n];
			for(int i = 0; i < res.length; i++)
				res[i] = nextLong();
			return res;
		}
		
		public double[] nextDoubleArray(int n)
		{
			double[] res = new double[n];
			for(int i = 0; i < res.length; i++)
				res[i] = nextLong();
			return res;
		}
		public void sortIntArray(int[] array)
		{
			Integer[] vals = new Integer[array.length];
			for(int i = 0; i < array.length; i++)
				vals[i] = array[i];
			Arrays.sort(vals);
			for(int i = 0; i < array.length; i++)
				array[i] = vals[i];
		}
		
		public void sortLongArray(long[] array)
		{
			Long[] vals = new Long[array.length];
			for(int i = 0; i < array.length; i++)
				vals[i] = array[i];
			Arrays.sort(vals);
			for(int i = 0; i < array.length; i++)
				array[i] = vals[i];
		}
		
		public void sortDoubleArray(double[] array)
		{
			Double[] vals = new Double[array.length];
			for(int i = 0; i < array.length; i++)
				vals[i] = array[i];
			Arrays.sort(vals);
			for(int i = 0; i < array.length; i++)
				array[i] = vals[i];
		}
	}
	
	static final int limite = 1000000000;
	
	static ArrayList <Long> luckys = new ArrayList <Long> ();
	
	static void generarLuckys(String acum)
	{
		if(acum.length() == 0 || Long.parseLong(acum) <= limite)
		{
			if(acum.length() != 0)
				luckys.add(Long.parseLong(acum));
			generarLuckys(acum + '4');
			generarLuckys(acum + '7');
		}
	}
	
	static long contar(int indiceA, int k, int pl, int pr, int vl, int vr)
	{
		if(indiceA + k - 1 >= luckys.size())
			return 0;
		long primero = luckys.get(indiceA);
		long segundo = luckys.get(indiceA + k - 1);
		long primeroAnt = indiceA == 0 ? 0L : luckys.get(indiceA - 1) + 1;
		long segundoSig = indiceA + k >= luckys.size() ? Integer.MAX_VALUE : luckys.get(indiceA + k) - 1;
		return cuantosHay(primeroAnt, primero, pl, pr) * cuantosHay(segundo, segundoSig, vl, vr) + cuantosHay(primeroAnt, primero, vl, vr) * cuantosHay(segundo, segundoSig, pl, pr);
	}
	
	private static long cuantosHay(long a, long b, long pl, long pr) 
	{
		long limiteSup = Math.min(b, pr);
		long limiteInf = Math.max(a, pl);
		if(limiteSup >= limiteInf)
			return limiteSup - limiteInf + 1;
		else
			return 0L;
	}

	public static void main(String[] args)
	{
		Scanner sc = new Scanner();
		generarLuckys("");
		Collections.sort(luckys);
		int pl = sc.nextInt();
		int pr = sc.nextInt();
		int vl = sc.nextInt();
		int vr = sc.nextInt();
		int k = sc.nextInt();
		long cuantos = 0;
		long cuantosTotal = ((long) ((pr - pl + 1))) * (vr - vl + 1);
		for(int i = 0; i < luckys.size(); i++)
			cuantos += contar(i, k, pl, pr, vl, vr);
		for(long l : luckys)
		{
			if(cuantosHay(l, l, pl, pr) == 1 && cuantosHay(l, l, vl, vr) == 1 && k == 1)
				cuantos--;
		}
		System.out.println((cuantos + 0.0d) / cuantosTotal);
		
	}
}