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

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$.