题目描述

有一个三棱锥，如下图所示。

有一只蚂蚁，它一开始在上方的顶点 $D$ 处。

他需要进行恰好 $n$ 次移动。

每次移动，它必须从当前所在的顶点沿着一条棱移动到另一个顶点。

求：$n$ 次移动恰好又回到起点（即顶点 $D$）的方案数？由于方案数很大，所以你只需要输出方案数模 $10^9+7$ 的结果即可。

输入格式

一个整数 $n(1 \le n \le 10^7)$。

输出格式

输出一个整数，表示蚂蚁沿着三棱锥的棱移动 $n$ 恰好又回到起点的方案数模 $10^9+7$ 的结果。

2

3

4

21

说明/提示

样例 1 解释

三种不同方案：

1. $D \rightarrow A \rightarrow D$
2. $D \rightarrow B \rightarrow D$
3. $D \rightarrow C \rightarrow D$

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$
• 对于 $50\%$ 的数据，$n \le 1000$
• 对于 $80\%$ 的数据，$n \le 10^5$
• 对于 $100\%$ 的数据，$1 \le n \le 10^7$