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

Limits: 2 sec., 256 MiB

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

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

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

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

Input

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

Output

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

Constraints

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

Samples

Input (stdin) сopy	Output (stdout) сopy
2	209

Notes

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