C++ :

#include<iostream>
using namespace std;
const int N(3001);
int f[N][N/2]={0};
void add(int *a,int *b,int *c,int *d)
{
    d[0]=a[0];
    for (int i=1;i<=d[0];i++)
    {
        d[i]+=a[i]+b[i]+c[i];
        d[i+1]+=d[i]/10;
        d[i]%=10;
    }
    if (d[d[0]+1]) d[0]++;
}
void init()
{
    f[1][0]=1; f[1][1]=1;
    f[2][0]=1; f[2][1]=2;
    f[3][0]=1; f[3][1]=4;
    for (int i=4;i<=3000;i++)
        add(f[i-1],f[i-2],f[i-3],f[i]);
}
void output(int n)
{
    for (int i=f[n][0];i>0;i--) cout<<f[n][i];
    cout<<endl;
}
        
int main()
{
    int n;
    init();
    while (cin>>n) output(n);
    return 0;
}