站外题求助

内存限制：$256$ $\text {MB}$ / 时间限制：$1$ 秒

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

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

单个整数表示 $n$。

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

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

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

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

输入 $1$，输出 $3$。

输入 $3$，输出 $6$。