{{{~cpp
#include <iostream>
using namespace std;
#include <vector>
int count;
unsigned int n[1001] = {1,2,5,};
int convert(int num)
{
	int temp = num;
	int l = 1;
	for(int i = 0; i < 3; i++)
	{
		if(temp%10 == 4)
			num -= 3*l;
		temp /= 10;
		l *= 10;			
	}
	return num;
}

int main()
{
	int num;
	vector<int> test;
	for(int i = 3; i <= 1000; i++)
		n[i] += 2*n[i-1] + n[i-2] + n[i-3];	
	for(int k =1; k < 30; k++)
		cout << n[k] << endl;

	while(cin >> num)
	{
//		num = convert(num);
		test.push_back(num);
	}
	for(vector<int>::iterator j = test.begin(); j != test.end(); j++)
		cout << n[*j] << endl;
	
	return 0;
}
}}}