import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.math.BigInteger; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.Scanner; public class Main { public static void main(String[] args) throws FileNotFoundException { long t = System.currentTimeMillis(); new Main().run(); System.err.println(System.currentTimeMillis() - t); } long pow(long a,long n) { long ret=1; for(;n>0;n>>=1,a*=a)if(n%2==1)ret*=a; return ret; } long comb(long n,long k) { if(n<0||k<0||n-k<0)return 0; long ret=1; for(long i=n;i>=n-k+1;--i)ret*=i; for(long i=k;i>=1;--i)ret/=i; return ret; } void run() { Scanner sc = new Scanner(System.in); int N=sc.nextInt(); long[][][] dp=new long[N+1][3][2]; dp[0][0][0]=1; for(int i=0;i