E. Тетраэдр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам задан тетраэдр. Обозначим его вершины буквами A, B, C и D соответственно.

В вершине тетраэдра D находится муравей. Муравей очень подвижный и не любит стоять на месте. В каждый момент времени он совершает один шаг от одной вершины к другой по некоторому ребру тетраэдра, оставаться на месте он не может.

От Вас в этой задаче требуется совсем немногое: нужно посчитать каким количеством способов муравей может прийти из исходной вершины D в себя ровно за n шагов. Другими словами, Вас просят узнать количество различных циклических путей длины n из вершины D в себя. Поскольку это количество может быть достаточно большим, ответ требуется посчитать по модулю 1000000007 (109 + 7).

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

В первой строке записано единственное целое число n (1 ≤ n ≤ 107) — требуемая длина циклического пути.

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

Выведите единственное целое число — искомое количество способов по модулю 1000000007 (109 + 7).

Примеры
Входные данные
2
Выходные данные
3
Входные данные
4
Выходные данные
21
Примечание

Искомые пути в первом примере:

  • D - A - D
  • D - B - D
  • D - C - D