/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.math.BigInteger;
import java.util.Arrays;

/**
 *
 * @author iZc <nplusc.de>
 */
public class Pfadevierschritt
{
    public static void main(String[] args)
    {
        System.out.println(calculatePaths(11));
    }
    
     public static BigInteger calculatePaths(int n)
    {
        //speichertabelle, aktuell und letzte
        BigInteger[][] table=new BigInteger[2][];//eine seite initialisieren mit leerem array (n modulo 2, gibt entweder 0 oder 1, nächster lauf wechselt
        table[n%2]=new BigInteger[n+1]; 
        Arrays.fill(table[n%2], BigInteger.ZERO);//array füllen
        table[n%2][0]=BigInteger.ONE;//eine zelle auf 1 seeded, da von def vorherigen reihe je 1 pfad hingeht // magie enthalten
        for(int x=n-1;x>=0;x--)//von rechts nach links scannen
        {
            //System.out.println("X="+x);
            BigInteger[] tableadd=new BigInteger[x+1];//tabellenspalte für neue werte
            Arrays.fill(tableadd, BigInteger.ZERO);//füllen
            BigInteger[] tabletouse = table[(x+1)%2];//tabellenspalte für spalte 1 rechts rausziehen
            for(int y=0;y<=x;y++)//hochwärts scannen
            {
                
                
                //arithmetik um innerhalb der grenzen zu bleiben
                if(y-4>=0)
                {
                   // System.out.println("-4");
                    tableadd[y]=tableadd[y].add(tabletouse[y-4]);
                }
                if(y-1>=0)
                {
                    //System.out.println("-1");
                    tableadd[y]=tableadd[y].add(tabletouse[y-1]);
                }
                //System.out.println("+-0");
                tableadd[y]=tableadd[y].add(tabletouse[y]);
                if(y+1<=x+1)
                {
                    //System.out.println("+1");
                    tableadd[y]=tableadd[y].add(tabletouse[y+1]);
                }
                if(y+4<=x+1)
                {
                    //System.out.println("+4");
                    tableadd[y]=tableadd[y].add(tabletouse[y+4]);
                }
            }
            table[x%2]=tableadd;
            //tabelle zurücknudeln
        }
        //rlement an 0|0 enthält das ergebnis
        return table[0][0];
    }
}