题目描述

石头剪刀布的游戏，每一轮可以出三种招数：石头、剪刀、布。给定一个整数 $N$，表示需要进行 $N$ 轮游戏。若规定每一轮出招不能与上一轮重复，请统计有多少种不同的出招序列？由于答案可能很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

单个整数 $N$

输出格式

3

12

数据范围

• 对于 $30\%$ 的数据，$1\leq N\leq 10$

• 对于 $60\%$ 的数据，$1\leq N\leq 1,000$

• 对于 $100\%$ 的数据，$1\leq N\leq 1,000,000,000$