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