Щаслива сума

Обмеження: 2 сек., 256 МіБ

Відомо, що щасливим числом є те, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 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}.\]

Вхідні дані

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

Вихідні дані

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

Обмеження

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 10	823799

Примітки

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