Щаслива послідовність Ту-є-Морзе
Limits: 2 sec., 256 MiB
Відомо, що щасливим числом є таке додатне ціле число, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.
Зеник має послідовність щасливих чисел {an}, що задовольняє такі умови.
a1=4.
Нехай bn — щасливе число, утворене заміною кожної четвірки в десятковому записі an на сімку, а сімки — на четвірку. Десятковий запис an+1 є конкатенацією десяткових записів an і bn.
Перші кілька елементів цієї послідовності: 4, 47, 4774, 47747447, …
Марічка хоче дізнатися значення an за модулем простого числа 109+7. Допоможіть їй.
Input
В одному рядку міститься ціле число n.
Output
В одному рядку виведіть an за модулем 109+7.
Constraints
1≤n≤105.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 | 47747447 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 | 682912129 |