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 PYTHON3):

Solution:
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
        )
        # print(get_good_segm_count(
        #     happies, happy_count, happy_window_ind,
        #     p_start, p_end, v_start, v_end
        # ), happy_window_ind)
    all_segments_count = (p_end - p_start + 1) * (v_end - v_start + 1)
    return good_segments_count / all_segments_count


print(main())