UVa 10918 - Tri Tiling

// UVa 10918 - Tri Tiling

#include <iostream>
#include <string.h>
using namespace std;

#define integer unsigned long long

int main() {
	int n;
	while (cin >> n && (n != -1)) {
		if (n & 1)
			cout << 0 << endl;
		else {
			integer T[31];
			T[0] = 1;
			for (int i = 2; i <= n; i += 2) {
				T[i] = T[i - 2] * 3;
				for (int j = i - 4; j >= 0; j -= 2)
					T[i] += (T[j] << 1);
			}
			cout << T[n] << endl;
		}
	}
	return 0;
}