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.

Difficulty: HARD
Tags: Complete search

Probability
Skill types: Complete search

Starter code:

Solutions:
import itertools as it
all_lucky = []
for length in range(1, 10):
	for comb in it.product(['7', '4'], repeat=length):
		all_lucky += [int(''.join(comb))]
all_lucky.sort()
(pl, pr, vl, vr, k) = map(int, input().split())
result = 0

def inters_len(a, b, c, d):
	(a, b) = sorted([a, b])
	(c, d) = sorted([c, d])
	return (max([a, c]), min([b, d]))

def check_for_intervals(pl, pr, vl, vr):
	global result
	for i in range(1, len(all_lucky) - k):
		(le, re) = (i, i + k - 1)
		(a, b) = inters_len(all_lucky[le - 1] + 1, all_lucky[le], pl, pr)
		left_len = max([0, b - a + 1])
		(c, d) = inters_len(all_lucky[re], all_lucky[re + 1] - 1, vl, vr)
		right_len = max([0, d - c + 1])
		result += left_len / (pr - pl + 1) * (right_len / (vr - vl + 1))
		if b == c and left_len * right_len > 1e-06:
			result -= 1 / (pr - pl + 1) / (vr - vl + 1) / 2
	(a, b) = inters_len(0, all_lucky[0], pl, pr)
	left_len = max([0, b - a + 1])
	(c, d) = inters_len(all_lucky[k - 1], all_lucky[k] - 1, vl, vr)
	right_len = max([0, d - c + 1])
	result += left_len / (pr - pl + 1) * (right_len / (vr - vl + 1))
	if b == c and left_len * right_len > 1e-06:
		result -= 1 / (pr - pl + 1) / (vr - vl + 1) / 2
	(a, b) = inters_len(all_lucky[-(k + 1)] + 1, all_lucky[-k], pl, pr)
	left_len = max([0, b - a + 1])
	(c, d) = inters_len(all_lucky[-1], 10 ** 9, vl, vr)
	right_len = max([0, d - c + 1])
	result += left_len / (pr - pl + 1) * (right_len / (vr - vl + 1))
	if b == c and left_len * right_len > 1e-06:
		result -= 1 / (pr - pl + 1) / (vr - vl + 1) / 2
if k != len(all_lucky):
	check_for_intervals(pl, pr, vl, vr)
	check_for_intervals(vl, vr, pl, pr)
else:
	(a, b) = inters_len(0, all_lucky[0], pl, pr)
	left_len = max([0, b - a + 1])
	(c, d) = inters_len(all_lucky[-1], 10 ** 9, vl, vr)
	right_len = max([0, d - c + 1])
	result += left_len / (pr - pl + 1) * (right_len / (vr - vl + 1))
	if b == c and left_len * right_len > 1e-06:
		result -= 1 / (pr - pl + 1) / (vr - vl + 1) / 2
	(a, b) = inters_len(0, all_lucky[0], vl, vr)
	left_len = max([0, b - a + 1])
	(c, d) = inters_len(all_lucky[-1], 10 ** 9, pl, pr)
	right_len = max([0, d - c + 1])
	result += left_len / (vr - vl + 1) * (right_len / (pr - pl + 1))
	if b == c and left_len * right_len > 1e-06:
		result -= 1 / (pr - pl + 1) / (vr - vl + 1) / 2
print(result)


import itertools

def generate_happy():
	happy_digits = '47'
	happies = []
	for num_len in range(1, 10):
		happies.extend(itertools.product(happy_digits, repeat=num_len))
	return [int(''.join(num)) for num in happies]

def clamp_segment(start, end, min_b, max_b):
	if start > end or min_b > max_b:
		raise ValueError(f'{start} {end} {min_b} {max_b}')
	if start > max_b or end < min_b:
		return (None, None)
	new_start = start
	new_end = end
	if start < min_b:
		new_start = min_b
	if end > max_b:
		new_end = max_b
	return (new_start, new_end)

def get_window_bounds(happies, happy_count, happy_window_ind):
	return (happies[happy_window_ind - 1] if happy_window_ind > 0 else 0, happies[happy_window_ind], happies[happy_window_ind + happy_count - 1], happies[happy_window_ind + happy_count] if happy_window_ind + happy_count < len(happies) else 10 ** 9 + 1)

def get_good_segm_count_ordered(lower_start, lower_end, upper_start, upper_end, prev_happy, this_happy, last_happy, next_happy):
	(lower_bound_start, lower_bound_end) = clamp_segment(lower_start, lower_end, prev_happy + 1, this_happy)
	(upper_bound_start, upper_bound_end) = clamp_segment(upper_start, upper_end, last_happy, next_happy - 1)
	if lower_bound_start is None or upper_bound_start is None:
		return 0
	return (lower_bound_end - lower_bound_start + 1) * (upper_bound_end - upper_bound_start + 1)

def get_good_segm_count(happies, happy_count, happy_window_ind, start_1, end_1, start_2, end_2):
	(prev_happy, this_happy, last_happy, next_happy) = get_window_bounds(happies, happy_count, happy_window_ind)
	first_is_lower_count = get_good_segm_count_ordered(start_1, end_1, start_2, end_2, prev_happy, this_happy, last_happy, next_happy)
	second_is_lower_count = get_good_segm_count_ordered(start_2, end_2, start_1, end_1, prev_happy, this_happy, last_happy, next_happy)
	this_happy = happies[happy_window_ind]
	if happy_count == 1 and start_1 <= this_happy <= end_2 and (start_2 <= this_happy <= end_2):
		second_is_lower_count -= 1
	return first_is_lower_count + second_is_lower_count

def main(args=None):
	if args is None:
		(p_start, p_end, v_start, v_end, happy_count) = map(int, input().split())
	else:
		(p_start, p_end, v_start, v_end, happy_count) = args
	happies = generate_happy()
	good_segments_count = 0
	for happy_window_ind in range(len(happies) - happy_count + 1):
		good_segments_count += get_good_segm_count(happies, happy_count, happy_window_ind, p_start, p_end, v_start, v_end)
	all_segments_count = (p_end - p_start + 1) * (v_end - v_start + 1)
	return good_segments_count / all_segments_count
print(main())


def gen(n, cur):
	if n == 0:
		global arr
		arr.append(cur)
	else:
		gen(n - 1, cur + '4')
		gen(n - 1, cur + '7')

def lseg(x1, x2):
	if x2 < x1:
		return 0
	return x2 - x1 + 1

def inter2(x1, x2, a, b):
	left = max(x1, a)
	right = min(x2, b)
	return (left, right)

def inter(x1, x2, a, b):
	(l, r) = inter2(x1, x2, a, b)
	return lseg(l, r)

def minus(a, b, c, d):
	d1 = (-1, c - 1)
	d2 = (d + 1, 10 ** 10)
	d1 = inter(a, b, *d1)
	d2 = inter(a, b, *d2)
	return d1 + d2
arr = []
for i in range(1, 11):
	gen(i, '')
arr = [0] + sorted(list(map(int, arr)))
(pl, pr, vl, vr, k) = map(int, input().split())
ans = 0
for start in range(1, len(arr) - k + 1):
	if arr[start + k - 1] > max(vr, pr):
		break
	if arr[start] < min(pl, vl):
		continue
	goleft = inter(pl, pr, arr[start - 1] + 1, arr[start])
	goright = inter(vl, vr, arr[start + k - 1], arr[start + k] - 1)
	(left, right) = (inter2(pl, pr, arr[start - 1] + 1, arr[start]), inter2(vl, vr, arr[start + k - 1], arr[start + k] - 1))
	ans += goleft * goright
	left1 = inter2(pl, pr, arr[start + k - 1], arr[start + k] - 1)
	right1 = inter2(vl, vr, arr[start - 1] + 1, arr[start])
	ans += minus(right1[0], right1[1], right[0], right[1]) * lseg(*left1)
	ans += (lseg(*right1) - minus(right1[0], right1[1], right[0], right[1])) * minus(left1[0], left1[1], left[0], left[1])
ans /= (pr - pl + 1) * (vr - vl + 1)
print(ans)


import itertools
(pl, pr, vl, vr, k) = map(int, input().split())
l = min(pl, vl)
r = max(pr, vr)
max_nr_digits = len(str(r))
lucky_numbers = []
for nr_digits in range(1, max_nr_digits + 1):
	lucky_numbers.extend((int(''.join(i)) for i in itertools.product('47', repeat=nr_digits)))
lucky_numbers = [nr for nr in lucky_numbers if l <= nr and nr <= r]
lucky_numbers.sort()
if len(lucky_numbers) < k:
	print('%.12f' % 0.0)
	exit()
lucky_numbers.insert(0, l - 1)
lucky_numbers.append(r + 1)
total_pairs = (pr - pl + 1) * (vr - vl + 1)
good_pairs = 0
for start_index in range(len(lucky_numbers) - k - 1):
	(a, b) = (lucky_numbers[start_index], lucky_numbers[start_index + 1])
	(c, d) = (lucky_numbers[start_index + k], lucky_numbers[start_index + k + 1])
	good_pairs += max(min(b, pr) - max(a + 1, pl) + 1, 0) * max(min(d - 1, vr) - max(c, vl) + 1, 0)
	good_pairs += max(min(b, vr) - max(a + 1, vl) + 1, 0) * max(min(d - 1, pr) - max(c, pl) + 1, 0)
	if b == c and pl <= b and (b <= pr) and (vl <= b) and (b <= vr):
		good_pairs -= 1
print('%.12f' % (good_pairs / total_pairs))


s = list()

def rec(x):
	if x > 100000000000:
		return
	s.append(x)
	rec(x * 10 + 4)
	rec(x * 10 + 7)

def f(l1, r1, l2, r2):
	l1 = max(l1, l2)
	r1 = min(r1, r2)
	return max(r1 - l1 + 1, 0)

def main():
	rec(0)
	s.sort()
	args = input().split()
	(pl, pr, vl, vr, k) = (int(args[0]), int(args[1]), int(args[2]), int(args[3]), int(args[4]))
	ans = 0
	i = 1
	while i + k < len(s):
		l1 = s[i - 1] + 1
		r1 = s[i]
		l2 = s[i + k - 1]
		r2 = s[i + k] - 1
		a = f(l1, r1, vl, vr) * f(l2, r2, pl, pr)
		b = f(l1, r1, pl, pr) * f(l2, r2, vl, vr)
		ans += a + b
		if k == 1 and a > 0 and (b > 0):
			ans -= 1
		i += 1
	all = (pr - pl + 1) * (vr - vl + 1)
	print(1.0 * ans / all)
main()


(vl, vr, pl, pr, k) = map(int, input().split())
lucky = [4, 7]
sz = 0
for i in range(1, 9):
	base = 10 ** i
	(psz, sz) = (sz, len(lucky))
	for j in [4 * base, 7 * base]:
		for pos in range(psz, sz):
			lucky.append(j + lucky[pos])
ans = 0
for i in range(0, len(lucky) - k + 1):
	(ll, lr) = (1 if i == 0 else lucky[i - 1] + 1, lucky[i])
	(rl, rr) = (lucky[i + k - 1], 1000000000 if i + k == len(lucky) else lucky[i + k] - 1)
	vc = max(0, min(vr, lr) - max(vl, ll) + 1)
	pc = max(0, min(pr, rr) - max(pl, rl) + 1)
	cnt1 = vc * pc
	vc = max(0, min(pr, lr) - max(pl, ll) + 1)
	pc = max(0, min(vr, rr) - max(vl, rl) + 1)
	cnt2 = vc * pc
	ans += cnt1 + cnt2
	if k == 1 and cnt1 > 0 and (cnt2 > 0):
		ans -= 1
print(ans / ((vr - vl + 1) * (pr - pl + 1)))