← 返回题目列表

Codeforces · 166/E

E. 四面体

中文机器翻译题面 查看原题

给你一个四面体。让我们用字母 A、B、C 和 D 相应地标记它的顶点。

一只蚂蚁站在四面体的顶点 D 上。蚂蚁很活跃,不会闲着的。在每一时刻,他都会沿着四面体的某些边缘从一个顶点到另一个顶点。蚂蚁就是不能站在一个地方。

你不必做太多事情来解决这个问题:你的任务是计算蚂蚁从初始顶点 D 到自身的路径数量,正好是 n 步。换句话说,要求你找出从顶点 D 到其自身长度为 n 的不同循环路径的数量。由于数字可能非常大,因此您应该将其打印为对 1000000007 (109 + 7) 取模。

输入

第一行包含唯一的整数 n (1 ≤ n ≤ 107) — 循环路径所需的长度。

输出

打印唯一的整数 — 所需的路数模 1000000007 (109 + 7)。

示例

输入 #1

2

输出 #1

3

输入 #2

4

输出 #2

21

注意

第一个示例中所需的路径是:

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