该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

单个整数表示 $n$。

输出格式

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

1

3

3

6

10

1026

数据规模与约定

对于 $30$ 的数据，$1 \leq n \leq 20$；

对于 $60$ 的数据，$1 \leq n \leq 1,000,000$；

对于 $100$ 的数据，$1 \leq n \leq 10^{18}$。