题目描述

有一个正四面体，四个顶点分别为 $A,B,C,D$，任意两个顶点之间都有一条边。

一只蚂蚁一开始在顶点 $D$。每一步，它必须沿着一条边走到另一个顶点，不能停在原地。

请计算恰好走 $n$ 步后，蚂蚁回到顶点 $D$ 的路径数量。答案对 $10^9+7$ 取模。

输入格式

输入一行一个整数 $n$，表示路径长度。

输出格式

输出一个整数，表示满足条件的路径数量对 $10^9+7$ 取模后的结果。

样例

2

3

4

21

说明

第一个样例中的路径为：

• $D-A-D$；
• $D-B-D$；
• $D-C-D$。

数据范围

$1\le n\le10^7$。