Щаслива послідовність Ту-є-Морзе
Обмеження: 2 сек., 256 МіБ
Відомо, що щасливим числом є таке додатне ціле число, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.
Зеник має послідовність щасливих чисел \(\{a_n\}\), що задовольняє такі умови.
\(a_1=4\).
Нехай \(b_n\) — щасливе число, утворене заміною кожної четвірки в десятковому записі \(a_n\) на сімку, а сімки — на четвірку. Десятковий запис \(a_{n+1}\) є конкатенацією десяткових записів \(a_n\) і \(b_n\).
Перші кілька елементів цієї послідовності: 4, 47, 4774, 47747447, …
Марічка хоче дізнатися значення \(a_n\) за модулем простого числа \(10^9+7\). Допоможіть їй.
Вхідні дані
В одному рядку міститься ціле число \(n\).
Вихідні дані
В одному рядку виведіть \(a_n\) за модулем \(10^9+7\).
Обмеження
\(1 \le n \le 10^5\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 | 47747447 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 | 682912129 |
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|