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

Обмеження: 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$.