记录编号	469587	评测结果	AAAAAAAAAA
题目名称	[FJOI 2007] 轮状病毒	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.224 s
提交时间	2017-11-03 15:38:08	内存使用	3.25 MiB

# define xmf 520
# include "stdio.h"
# include "math.h"
# include "algorithm"
# include "string.h"
# include "iostream"

using namespace std;

# define L 10000000
# define int long long

void read(int &x){
	 x=0;char c=getchar();
	 while(c<'0'||c>'9') c=getchar();
	 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}

struct BIGNUM{
	   int s[100005],len;
	   BIGNUM(){len=1;memset(s,0,sizeof s);}
	   bool operator < (const BIGNUM &A)const{
	   		if(len!=A.len) return len<A.len;
	   		for(int i=len-1;i>=0;i--)
	   			if(s[i]<A.s[i]) return true;
	   		return false;
	   }
	   bool operator == (const BIGNUM &A)const{return (!(*this<A)&&!(A<*this));}
	   bool operator != (const BIGNUM &A)const{return *this<A||A<*this;}
	   bool operator > (const BIGNUM &A)const{return A<*this;} 
	    BIGNUM operator * (const int x){
	   	    BIGNUM c,d=*this;
	   	    int jw=0;
	   	    c.len=d.len+1;
	   	    for(int i=0;i<c.len;i++){
	   	    	c.s[i]=(d.s[i]*x+jw)%L;
	   	    	jw=(d.s[i]*x+jw)/L;
	   	    }
	   	    while(c.s[c.len-1]==0) c.len--;
	   	    return c;
	   } 
	   BIGNUM operator + (const int x){
              BIGNUM d=*this,c;
	   	      int jw=x;
	   	      c.len=d.len+1;
	   	      for(int i=0;i<=c.len;i++){
	   	      	    c.s[i]=(d.s[i]+jw)%L;
	   	      	    jw=(d.s[i]+jw)/L;
	   	      }while(c.s[c.len-1]==0) c.len--;
	   	      return c;
       }
       BIGNUM operator - (BIGNUM &x)const{
              BIGNUM c,d=*this;
	   	      int jw=0;
	   	      c.len=d.len+1;
	   	      for(int i=0;i<=c.len;i++){
	   	      	  if(d.s[i]<x.s[i]){
	   	      	  	 d.s[i]+=L;
	   	      	  	 c.s[i]=d.s[i]-x.s[i];
	   	      	  	 d.s[i+1]--;
	   	      	  }
	   	      	  else c.s[i]=d.s[i]-x.s[i];
	   	      	  
	   	      }while(c.s[c.len-1]==0) c.len--;
	   	      return c;
       }
	   void in(){
	   	    char sa[100005];
	   	    scanf("%s",sa);
	   	    int now=0,cc=0,tot=0,sh=1;
			for(int i=strlen(sa)-1;i>=0;i--){
	   	    	tot+=(sa[i]-'0')*sh;
	   	    	sh*=10;cc++;
	   	    	if(cc==7){
	   	    		s[now++]=tot;
	   	    		sh=1;
	   	    		cc=tot=0;
	   	    	}
	   	    }
	   	    if(tot) s[now++]=tot;
	   	    len=now;
	   }
	   void out(){
	   		printf("%lld",s[len-1]);
	   		for(int i=len-2;i>=0;i--)
	   			printf("%0*lld",7,s[i]);
	   }
}A,B,C;

int n;

signed main(){
	freopen("bzoj_1002.in","r",stdin);
	freopen("bzoj_1002.out","w",stdout);
	read(n);
	A.len=1,A.s[0]=1;
	B.len=1,B.s[0]=5;
	for(int i=3;i<=n;i++){
		if(i&1){
			C=B*3;
			A=C-A;
			A=A+2;
		}
		else{
			C=A*3;
			B=C-B;
			B=B+2;
		}
	}
	if(n&1) A.out();
	else B.out();
}