Щаслива сума

Limits: 2 sec., 256 MiB

Відомо, що щасливим числом є те, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.

Нехай \(S\) — множина щасливих чисел не менших ніж \(a\) та не більших ніж \(b\): \[S = \left\{ n: \quad a \le n \le b, \quad n \text{ --- щасливе число} \right\}.\]

Ваше завдання — обчислити остачу від ділення на просте число 1234567891 такої суми: \[\sum_{n \in S}{n^n}.\]

Input

Єдиний рядок містить два цілих числа \(a\) та \(b\) — межі проміжку.

Output

У єдиному рядку виведіть ціле число — остачу від ділення щасливої суми на 1234567891.

Constraints

\(1 \le a \le b \le 10^{18}\).

Samples

Input (stdin) сopy	Output (stdout) сopy
1 10	823799

Notes

\(4^4 + 7^7 = 823799\).