给你一个四面体。让我们用字母 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