题目描述

石头剪刀布 $N$ 轮，每轮不能与上一轮相同。求不同出招序列数，模 $10^9+7$。

输入格式

单个整数 $N$。

数据范围

$1 \leq N \leq 10^9$。

样例

输入

3

输出

12