#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <iostream>

#include <gmpxx.h>
#define big mpz_class

big countTrees(const int, const int );

int minHeight( int x ) {
	int res = 0;
	int c = 1;
	while( c <= x ) {
		c = c << 1;
		++res;
	}
	return res;
}

int main( int argc, char* argv[] ) {
	if ( argc == 1 ) {
		printf("Usage: <#Elements> <Height>\n");
		printf("       <max #Elements> (calculates all average heights)\n" );   
		return -1;
	}

	if ( argc == 2 ) {
		int max = atoi(argv[1]);
		big numTrees = 0;
		big heightSum = 0;

		std::cout << "0\t1\t0\t0" << std::endl;
		for( int n = 1; n <= max; n++ ) {
			big last = countTrees(n,-1);
			for( int h = 0; h <= n; h++ ) {
				big res = countTrees( n, h );
				big temp = res-last;
				last = res;
				res = temp;

				numTrees += res;
				heightSum += res*h;
			}

			mpq_class average( heightSum, numTrees  );
			mpf_class f( average );

			std::cout << n << "\t" << numTrees << "\t" << heightSum << "\t" << f << std::endl;
			numTrees = 0;
			heightSum = 0;
		}
	} else if ( argc == 3 ) {
		int n = atoi(argv[1]);
		int h = atoi(argv[2]);

		if ( h > n ) {
			printf("0 \n");
		} else {
			big countA = countTrees( n, h );
			big countB = countTrees( n, h-1 );
			std::cout << countA-countB << std::endl;
		}
	}
	return 0;
}

big countTrees( const int n, const int height ) {
	if ( n == 0 ) { 
		return 1;
	}
	
	if ( height < minHeight(n) || height > n ) {
		return 0;
	}

	big** table = new big*[n+1];
	for( int k = 0; k < n+1; k++ ) {
		table[k] = new big[height+1];
		for( int h = 0; h < height+1; h++ ) {
			table[k][h] = (k == 0) ? 1 : 0;
		}
	}
	
	for( int h = 1; h <= height; h++ ) {
		for( int i = 1; i <= n; i++ ){
			big count = 0;
			for( int k = 1; k <= i; k++ ) {
				count += table[k-1][h-1]*table[i-k][h-1];
			}
			table[i][h] = count;
		}
	}

	big res = table[n][height];

	// Clean up
	for( int k = 0; k < n+1; k++ ) {
		delete[] table[k];
	}
	delete[] table;

	return res;
}