Гномы посадили очень интересное растение, представляющее собой треугольник, направленный «вверх». Это растение обладает забавным свойством. Через один год растение-треугольник, направленное «вверх», разделится на четыре растения-треугольника: три из них будут направлены «вверх», а одно — «вниз». Через еще один год каждое растение-треугольник, разделится на четыре растения-треугольника: три из них направлены в ту же сторону, что и родительское растение, а одно направлено в другую сторону. Далее каждый год процесс повторяется. На рисунке ниже показан этот процесс.
Помогите гномам узнать, сколько получится растений-треугольников, смотрящих «вверх», через n лет.
Выходные данные
Выведите единственное число — остаток от деления количества смотрящих «вверх» растений через n лет на 1000000007 (109 + 7).
Примечание
Первый тестовый пример, соответствует второму треугольнику на рисунке в условии. Второй тестовый пример — третьему.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
3
|
|
2
|
2
|
10
|