开通账号请联系(微信号:13867980053)- 金华熊老师
问题 E: 上海市2023年2月月赛-丙组-第5题-圆环三染色

问题 E: 上海市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