1328: 圆环三染色
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：54
Solved：4
Description
有一个圆环上有 $n$ 个点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。
请求出有多少种染色方案。答案可能很大，输出模 $1,000,000,007$ 的余数。
环上每个点都是独特的。
请求出有多少种染色方案。答案可能很大，输出模 $1,000,000,007$ 的余数。
环上每个点都是独特的。
Input
- 单个整数表示 $n$。
Output
- 表示方案数模 $1,000,000,007$ 的余数。
Sample Input Copy
1Sample Output Copy
3HINT
数据范围
- 对于 $30\%$ 的数据，$1≤n≤20$；
- 对于 $60\%$ 的数据，$1≤n≤1,000,000$；
- 对于 $100\%$ 的数据，$1≤n≤10^{18}$
- 对于 $30\%$ 的数据，$1≤n≤20$；
- 对于 $60\%$ 的数据，$1≤n≤1,000,000$；
- 对于 $100\%$ 的数据，$1≤n≤10^{18}$