A. Травяное растение
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Гномы посадили очень интересное растение, представляющее собой треугольник, направленный «вверх». Это растение обладает забавным свойством. Через один год растение-треугольник, направленное «вверх», разделится на четыре растения-треугольника: три из них будут направлены «вверх», а одно — «вниз». Через еще один год каждое растение-треугольник, разделится на четыре растения-треугольника: три из них направлены в ту же сторону, что и родительское растение, а одно направлено в другую сторону. Далее каждый год процесс повторяется. На рисунке ниже показан этот процесс.

Помогите гномам узнать, сколько получится растений-треугольников, смотрящих «вверх», через n лет.

Входные данные

В первой строке задано единственное целое число n (0 ≤ n ≤ 1018) — количество полных лет, которое росло растение.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Выходные данные

Выведите единственное число — остаток от деления количества смотрящих «вверх» растений через n лет на 1000000007 (109 + 7).

Примеры
Входные данные
1
Выходные данные
3
Входные данные
2
Выходные данные
10
Примечание

Первый тестовый пример, соответствует второму треугольнику на рисунке в условии. Второй тестовый пример — третьему.