C++

#include <cstdio>

#include <cstring>

using namespace std;

int dt[10010];

int serch(int n){

    if(n==0){

        return 1;

    }

    if(n<0){

        return 0;

    }

    if(dt[n]!=-1)

        return dt[n];

    int result=0;

    for(int i=0;i<=n-3;i++){

        result = (result + serch(i))%1000;

    }

    return dt[n]=(serch(n-1)*2+serch(n-2)*5+result*4)%1000;

}

int main()

{

    memset(dt,-1,sizeof(dt));

    int N;

    scanf("%d",&N);

    printf("%d",serch(N));

    return 0;

}