Pasted

 
import java.math.BigInteger;
 
public class DUDU2 {
 
    public static void main(String[] args) {
 
        // type in here your number for n
        int n = 5555;
 
        // this for loop is optional. it shows you every calculation from 5 to n
        for (int i = 1188; i <= n; i++) {
 
            BigInteger[][][][] E = new BigInteger[2 * i][2 * i + 3][5][4];
 
            // fill BigInteger array with zeros to avoid NullPointerExceptions
            for (int c = 0; c < E.length; c++) {
                for (int v = 0; v < E[0].length; v++) {
                    for (int b = 0; b < E[0][0].length; b++) {
                        for (int f = 0; f < E[0][0][0].length; f++) {
                            E[c][v][b][f] = BigInteger.ZERO;
                        }
                    }
                }
            }
            
            // first Up in the path is static, so we give it a 1
            E[0][2][1][0] = BigInteger.ONE;
 
            // loops through the path and checks for specific ending patterns
            for (int x = 1; x < 2 * i; x++) {
                for (int s = (x + 1) % 2; s < x + 2; s += 2) {
                    for (int a = 0; a <= 2; a++) {
                        E[x][s + 1][a + 1][0] = E[x - 1][s][a + 1][0].add(E[x - 1][s][a + 1][2]);
                        E[x][s + 1][a + 1][1] = E[x - 1][s + 2][a + 1][0]
                                .add(E[x - 1][s + 2][a + 1][1].add(E[x - 1][s + 2][a + 1][3]));
                        E[x][s + 1][a + 1][2] = E[x - 1][s][a][3].add(E[x - 1][s][a + 1][1]);
                        E[x][s + 1][a + 1][3] = E[x - 1][s + 2][a + 1][2];
                    }
                }
            }
 
            BigInteger sum = BigInteger.ZERO;
 
            // sums up the results and prints them out
            for (int x = 0; x < 4; x++) {
                sum = sum.add(E[2 * i - 1][1][3][x]);
            }
            System.out.println("n=" + i + ": " + sum);
        }
    }
}