Codeforces Round 118 (Div. 1) |
---|
Закончено |
Гномы посадили очень интересное растение, представляющее собой треугольник, направленный «вверх». Это растение обладает забавным свойством. Через один год растение-треугольник, направленное «вверх», разделится на четыре растения-треугольника: три из них будут направлены «вверх», а одно — «вниз». Через еще один год каждое растение-треугольник, разделится на четыре растения-треугольника: три из них направлены в ту же сторону, что и родительское растение, а одно направлено в другую сторону. Далее каждый год процесс повторяется. На рисунке ниже показан этот процесс.
Помогите гномам узнать, сколько получится растений-треугольников, смотрящих «вверх», через n лет.
В первой строке задано единственное целое число n (0 ≤ n ≤ 1018) — количество полных лет, которое росло растение.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
Выведите единственное число — остаток от деления количества смотрящих «вверх» растений через n лет на 1000000007 (109 + 7).
1
3
2
10
Первый тестовый пример, соответствует второму треугольнику на рисунке в условии. Второй тестовый пример — третьему.
Название |
---|