Description

有一个圆环上有 <math xmlns="http://www.w3.org/1998/Math/MathML">n 个点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。

请求出有多少种染色方案。答案可能很大，输出模 <math xmlns="http://www.w3.org/1998/Math/MathML">1,000,000,007 的余数。

Input Format

• 单个整数表示 <math xmlns="http://www.w3.org/1998/Math/MathML">n。

Output Format

• 表示方案数模 <math xmlns="http://www.w3.org/1998/Math/MathML">1,000,000,007 的余数。

1

3

Hint

样例输入：2

样例输出：6

• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">30% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n≤20；
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">60% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n≤1,000,000；
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">100% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n≤1018

Source

数论 快速幂 上海市2023年2月赛