题目描述

有一个圆环上有 $n$ 个点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。

请求出有多少种染色方案。答案可能很大，输出模 $1,000,000,007$ 的余数。

输入格式

• 单个整数表示 $n$。

输出格式

• 表示方案数模 $1,000,000,007$ 的余数。

1

3

3

6

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 1,000,000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 10^{18}$