1.
/**
* Angewandte Mathematik, SS11
* Problem: 10312 - Expression Bracketing
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1253
*
* @author Markus Schöllner
* @author Andreas Maier
* @version 1.0, 07/03/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.300
*/

import java.math.BigInteger;
import java.util.Scanner;

//Version Accepted
public class Main {

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

BigInteger result[] = new BigInteger[27];
result[1] =BigInteger.valueOf(0);
result[2] =BigInteger.valueOf(0);
result[3] =BigInteger.valueOf(1);
result[4] =BigInteger.valueOf(6);
result[5] =BigInteger.valueOf(31);
result[6] =BigInteger.valueOf(155);
result[7] =BigInteger.valueOf(771);
result[8] =BigInteger.valueOf(3850);
result[9] =BigInteger.valueOf(19363);
result[10] =BigInteger.valueOf(98187);
result[11] =BigInteger.valueOf(502063);
result[12] =BigInteger.valueOf(2587937);
result[13] =BigInteger.valueOf(13440857);
result[14] =BigInteger.valueOf(70296473);
result[15] =BigInteger.valueOf(370019079);
result[16] =BigInteger.valueOf(1959106674);
result[17] = new BigInteger("10428220683");
result[18] = new BigInteger("55779368219");
result[19] = new BigInteger("299681788263");
result[20] = new BigInteger("1616594895397");
result[21] = new BigInteger("8752745540025");
result[22] = new BigInteger("47550361333961");
result[23] = new BigInteger("259124455145823");
result[24] =new BigInteger("1416118615851221");
result[25] =new BigInteger("7759443920290221");
result[26] =new BigInteger("42620109348084205");

while(input.hasNext()){

System.out.println(result[input.nextInt()]);
}
}

/* ----------------------------------------------------
* Eigentliche Berechnung, bekommt allerdings Time Limit Exceeded
* ----------------------------------------------------
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
BigInteger superCata,normCata;

int n;

while(input.hasNext()){
n= input.nextInt();
superCata = superCatalan(n+1).abs();
normCata = Catalan(n);
System.out.println(superCata.subtract(normCata));
}
}

public static BigInteger superCatalan(int n){
BigInteger result,firstPart,secondPart;
if(n>0){
firstPart = BigInteger.valueOf(3*(2*n-3));
firstPart = firstPart.multiply(superCatalan(n-1));
secondPart = BigInteger.valueOf(n-3);
secondPart = secondPart.multiply(superCatalan(n-2));
result = firstPart.subtract(secondPart);
result = result.divide(BigInteger.valueOf(n));
}
else{
return BigInteger.ONE;
}
return result;

}

public static BigInteger Catalan(int n){
BigInteger result = BigInteger.ONE;
BigInteger nFak = BigInteger.ONE;
int numerator = 2*n;
int denumerator = n+2;
if(n>1){
for(int c = denumerator; c<=numerator; c++){
result = result.multiply(BigInteger.valueOf(c));
}
for(int c =2;c<=n;c++){
nFak = nFak.multiply(BigInteger.valueOf(c));
}
result = result.divide(nFak);
}
else return BigInteger.ONE;
return result;
}
*/
}