问题描述

今天何老板得到了一个神奇的正三角形，它具有自动分形技能。
一天后，它会分成4个相同的正三角形，其中三个“尖尖”朝上，一个“尖尖”朝下。
一天后，里面的每个三角形又会按上述规则分形下去。
如此反复......
何老板想知道，在n天后，总共有多少个“尖尖”朝上的三角形。

分形过程如下图所示，2天后，有10个“尖尖”朝上的三角形。

输入格式

一行，一个整数n

输出格式

一行，一个整数，表示计算结果， mod 1000000007后再输出。

样例输入 1

1

样例输出 1

3

样例输入 2

2

样例输出 2

10

样例输入 3

11

样例输出 3

2098176

#include<iostream>
#define p 1000000007
using namespace std;
int ksm(long long a,long long b,long long c)
{long long ans=1;a%=c;while(b>0){if(b&1)ans=(ans*a)%c;b>>=1;a=(a*a)%c;}return ans;
}
int main()
{long long n;cin>>n;if(n==1)cout<<3;else{long long cnt=ksm(2,n-1,p);long long sum=ksm(2,2*n-1,p);cout<<(cnt+sum)%p;}
}