Щасливі числа без послідовних четвірок

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

Сьогодні всі святкують День Щасливих Чисел!

Одна з традиційних справ, яку роблять цього дня – перевірка різних властивостей щасливих чисел.

Усім відомо, що число є щасливим, якщо його десятковий запис містить лише цифри 4 та 7. Марічка вважає щасливе число чудовим, якщо в ньому немає двох четвірок підряд.

А якою є сума всіх чудових чисел, десятковий запис яких містить щонайбільше \(n\) цифр? Оскільки дане значення може бути дуже великим – знайдіть остачу від ділення відповіді на \(10^9+7\).

Вхідні дані

У єдиному рядку задано одне ціле число \(n\) – максимальна довжина десяткового запису чудового щасливого числа.

Вихідні дані

У єдиному рядку виведіть суму чудових щасливих чисел за модулем простого числа \(10^9 + 7\).

Обмеження

\(1 \le n \le 10^{18}\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2	209

Примітки

Єдине щасливе число довжиною \(\le\) 2, яке не є чудовим – 44. Тому сума \(=4+7+47+74+77=209\).