Щаслива сума
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) | Output (stdout) |
|---|---|
| 1 10 | 823799 |
Notes
\(4^4 + 7^7 = 823799\).
Source: Змагання Шефа 11
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|