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.*;
import java.io.*;
import java.math.BigInteger;
import static java.lang.Math.*;

public class Sol implements Runnable {
	ArrayList <Long> luckyList = new ArrayList <Long> ();
	final long INF = 10000000000L;

	void go(long u) {
		if (u > INF) return;
		luckyList.add(u);
		go(u * 10 + 4);
		go(u * 10 + 7);				
	}

	long intersect(long x1, long y1, long x2, long y2) {
		long L = max(x1, x2);
		long R = min(y1, y2);
		if (L > R) return 0;
		return R - L + 1;
	}

	boolean contains(long x, long y, long q) {
		return x <= q && q <= y;
	}

	int brute(long x1, long y1, long x2, long y2, int k) {
		int ret = 0;
		for (long x = x1; x <= y1; x++) {
			for (long y = x2; y <= y2; y++) {
				int cnt = 0;
				long p1 = min(x, y);
				long p2 = max(x, y);
				for (long v: luckyList) {
					if (contains(p1, p2, v)) {
						cnt++;
					}
				}
				if (cnt == k) ret++;
			}
		}
		debug(ret);
		return ret;
	}

	void solve() throws Exception {
		long pl = nextInt();
		long pr = nextInt();
		long vl = nextInt();
		long vr = nextInt();
		int k = nextInt();

		go(0);
		int n = luckyList.size();
		long [] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = luckyList.get(i);
		}	
		Arrays.sort(a);

		long ans = 0;
		for (int i = 1; i + k < n; i++) {
			long fl = a[i - 1] + 1;
			long fr = a[i];
			long sl = a[i + k - 1];
			long sr = a[i + k] - 1;
			ans += intersect(pl, pr, fl, fr) * intersect(vl, vr, sl, sr);
			ans += intersect(pl, pr, sl, sr) * intersect(vl, vr, fl, fr);
			if (k == 1 && contains(pl, pr, a[i]) && contains(vl, vr, a[i])) ans--;
		} 

		//brute(pl, pr, vl, vr, k);
		//debug(ans);

		double ret = ans * 1.0 / (pr - pl + 1) / (vr - vl + 1);
		out.printf("%.11f", ret);
	}

	public static void main(String[] args) {
		new Thread(new Sol()).start();
	}

	public void run() {
		try {
			Locale.setDefault(Locale.US);
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sTime();
			solve();
			debug("Time consumed: " + gTime());
			gMemory();

			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	
	StringTokenizer tokenizer = new StringTokenizer("");
	BufferedReader in;
	PrintWriter out;
	long time;

	void sTime() {
		time = System.currentTimeMillis();
	}

	long gTime() {
		return System.currentTimeMillis() - time;
	}

	void gMemory() {
		debug("Memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1000 + " kb");
	}

	public void debug(Object o) {
		System.err.println(o);
	}
	
	boolean seekForToken() {
		while (!tokenizer.hasMoreTokens()) {
			String s = null;
			try {
				s = in.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			if (s == null)
				return false;
			tokenizer = new StringTokenizer(s);
		}
		return true;
	}

	String nextToken() {
		return seekForToken() ? tokenizer.nextToken() : null;
	}

	int nextInt() {
		return Integer.parseInt(nextToken());
	}

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}

	BigInteger nextBig() {
		return new BigInteger(nextToken());
	}
}