问题2180--上海市2023年2月月赛-丙组-第5题-圆环三染色

2180: 上海市2023年2月月赛-丙组-第5题-圆环三染色

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

有一个圆环上有n个不同的点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。
请求出有多少种染色方案。答案可能很大，输出模1,000,000,007的余数。

输入

单个整数表示n
1≤n<1018

输出

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

样例输入 Copy 

1

样例输出 Copy 

3

提示

更多样例：
如果输入3，那么输出时6

来源/分类

40动态规划杂类 
[提交] [状态]