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:
//package e_contest_10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class luckyProbability {
	static TreeSet<Long> lucky;

	static void gen(String cur) {
		long ans = 0;
		for (int i = 0; i < cur.length(); i++) {
			if (cur.charAt(i) == '1') {
				ans = ans * 10 + 7;
			} else
				ans = ans * 10 + 4;
		}
		lucky.add(ans*1l);
	}
	static class pair{
		long start = 0;
		long end = 0;
		public pair(long start, long end) {
			this.start = start;
			this.end = end;
		}
		public long overlap(pair sec) {
//			i/f()
			long maxStart = Math.max(sec.start, start);
			long minEnd = Math.min(sec.end, end);
			if(minEnd<maxStart)
				return 0;
			return minEnd-maxStart+1;
		}
		public pair intersect(pair sec) {
			long maxStart = Math.max(sec.start, start);
			long minEnd = Math.min(sec.end, end);
			if(minEnd<maxStart)
				return null;
			return new pair(maxStart,minEnd);
		}
		public String toString() {
			return start+" "+end;
		}

	}
	static int gen2(String cur) {
		int ans = 0;
		for (int i = 0; i < cur.length(); i++) {
			if (cur.charAt(i) == '1') {
				ans = ans * 10 + 7;
			} else
				ans = ans * 10 + 4;
		}
		return (ans);
	}
	static int INF = -1*(int)1e9;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int pl = sc.nextInt(), pr = sc.nextInt(), vl = sc.nextInt(), vr = sc.nextInt(), k = sc.nextInt();
		int min =0;
		int max = (int)1e9+1;
		lucky = new TreeSet<Long>();
		int lenMin = ((min) + "").length();
		int lenMax = ((max) + "").length();
//		 System.out.println(lenMin+" "+lenMax);
		for (int i = lenMin; i <= lenMax; i++) {
			long start = 0;
			long end = (long) Math.pow(2, i);
			// System.out.println(i+" "+start+" "+end);
			while (start < end) {
				String cur = Long.toBinaryString(start);
				while (cur.length() < i)
					cur = "0" + cur;
				gen(cur);
				start++;
//				if(start<0)
//					System.out.println(i);
			}
		}
		lucky.add(0l);
		lucky.add(444444444l);
		// System.out.println(lucky.toString());
		// lenMin ok so what do we do now????
//		System.out.println(lucky.toString());
		long[] ans = new long[lucky.size()];
		int idx = 0;
		for (long i : lucky) {
			ans[idx++] = i;
		}
		if (ans.length < k) {
			System.out.println(0);
		} else {
			double valid1 = 0;
			// int
			long counter = 0;
			pair p = new pair(pl, pr);
			pair v=  new pair(vl, vr);
			for (int i = 1; i < ans.length - k; i++) {
				long liPrev = (int)ans[i-1]+1;
				long lI = (int)ans[i];
				double count2 = 0;
				double count1 = 0;
				pair intersect1 = p.intersect(new pair(liPrev, lI));
				count1 = p.overlap(new pair(liPrev, lI));
				long two = ans[i + k - 1];
				long twoNext = ans[i+k]-1;
				pair intersect2 = v.intersect(new pair(two,twoNext));
				count2 = v.overlap(new pair(two,twoNext));
				counter = intersect1!=null&intersect2!=null?intersect1.overlap(intersect2):0;
//				if(counter!=0)
//					System.out.println("hello");
//				System.out.println(liPrev+" "+lI+" "+two+" "+twoNext+" "+count1+" "+count2+" "+counter);
				//				System.out.println((one <= pr) + " " + (one >= pl) + " " + vl + " " + pl);
//				System.out.println(intersect1.toString()+" "+intersect2.toString()+" "+counter);
				valid1 += (count1 * count2-counter)/((vr-vl+1)*1.0*(pr-pl+1));
//				System.out.println(prevL+" "+one +" "+two+" "+lastR+" "+count1+" "+count2);
//				 System.out.println(prevL+" "+one +" "+two+" "+lastR+" "+count1+" "+count2
				// "+valid1);
//				valid1/=
				
			}//(6,7) (7,8) 
			p = new pair(vl, vr);
			v = new pair(pl,pr);
			for (int i = 1; i < ans.length - k; i++) {
				long liPrev = ans[i-1]+1;
				long lI = ans[i];
				double count2 = 0;
				double count1 = 0;
				count1 = p.overlap(new pair(liPrev, lI));
				long two = ans[i + k - 1];
				long twoNext = ans[i+k]-1;
				count2 = v.overlap(new pair(two,twoNext));
				//				System.out.println((one <= pr) + " " + (one >= pl) + " " + vl + " " + pl);
//				System.out.println(liPrev+" "+lI+" "+two+" "+twoNext+" "+count1+" "+count2);
				valid1 += (count1 * count2)/((vr-vl+1)*1.0*(pr-pl+1));
//				System.out.println(prevL+" " +" "+two+" "+lastR+" "+count1+" "+count2);
//				 System.out.println(prevL+" "+one +" "+two+" "+lastR+" "+count1+" "+count2
				// "+valid1);
//				valid1/=
				
			}//(6,7) (7,8) //			System.out.println(valid1);
			System.out.println(valid1);
//			System.out.println(lucky.toString());
//			System.out.println(ans.length);
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}