Happy sum

It is known that the number is happy, if its decimal notation contains only fours and sevens. For example, the numbers 4, 7, 47, 7777 and 4744474 are happy.

Let S be the set of happy numbers, no less than a and no more than b: S = {n : a ≤ n ≤ b, n is happy}. Calculate the remainder of dividing by 1234567891 the next sum:

Input

Two integers a and b (1 ≤ a ≤ b ≤ 10^18).

Output

Output the remainder of dividing the lucky sum by 1234567891.

Examples

Note

4^4 + 7^7 = 823799.