记录编号	546000	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	3264.魔法部落	最终得分	100
用户昵称	发光二向箔	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2019-11-04 22:27:48	内存使用	13.66 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const ULL mod=1000000007;
ULL Power(ULL n)
{
   	ULL ans;
   	if(n==0)return 1;
   	if(n&1)return 3*Power(n-1)%mod;
   	else{
    	ans=Power(n/2);
    	return ((ans%mod)*(ans%mod))%mod; 
   	} 
}
ULL powersummod(ULL n)
{
  	if(n==1)return 3;
   	ULL s=powersummod((n/2));
   	ULL ans=(s+s*Power((n/2)))%mod;
   	if(n&1)
   	{
   		ans=(ans+Power(n))%mod;
   	}
   	return ans;
   }
int main()
{
   	freopen("magicd.in","r",stdin);
   	freopen("magicd.out","w",stdout);
   	ULL n;
   	cin>>n;
   	ULL s=powersummod(n)+1;
   	cout<<s<<endl;
   	return 0;
}