?

f[n]=3*f[n-1]-f[n-2]+2

?

Description

给定n(N<=100)，编程计算有多少个不同的n轮状病毒。

Input

第一行有1个正整数n。

Output

将编程计算出的不同的n轮状病毒数输出

Sample Input

Sample Output

?

?

?

/**************************************************************
    Problem: 1002
    User: CKboss
    Language: Java
    Result: Accepted
    Time:888 ms
    Memory:14824 kb
****************************************************************/
 
import java.util.*;
import java.math.*;
 
 
public class Main {
     
    BigInteger[] ct = new BigInteger[120];
     
    void init(){
        ct[1]=BigInteger.valueOf(1);
        ct[2]=BigInteger.valueOf(5);
        ct[3]=BigInteger.valueOf(16);
         
        for(int i=4;i<=100;i++){
            ct[i]=ct[i-1].multiply(BigInteger.valueOf(3)).subtract(ct[i-2]).add(BigInteger.valueOf(2));
        }
    }
     
    Main(){
        Scanner in = new Scanner(System.in);
        init();
        int n=in.nextInt();
        System.out.println(ct[n]);
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new Main();
    }
 
}

?