Codeforces Round 113 (Div. 2) |
---|
Закончено |
Вам задан тетраэдр. Обозначим его вершины буквами A, B, C и D соответственно.
В вершине тетраэдра D находится муравей. Муравей очень подвижный и не любит стоять на месте. В каждый момент времени он совершает один шаг от одной вершины к другой по некоторому ребру тетраэдра, оставаться на месте он не может.
От Вас в этой задаче требуется совсем немногое: нужно посчитать каким количеством способов муравей может прийти из исходной вершины D в себя ровно за n шагов. Другими словами, Вас просят узнать количество различных циклических путей длины n из вершины D в себя. Поскольку это количество может быть достаточно большим, ответ требуется посчитать по модулю 1000000007 (109 + 7).
В первой строке записано единственное целое число n (1 ≤ n ≤ 107) — требуемая длина циклического пути.
Выведите единственное целое число — искомое количество способов по модулю 1000000007 (109 + 7).
2
3
4
21
Искомые пути в первом примере:
Название |
---|