C++

#include <cstdio>

#include <cstring>

using namespace std;

int dt[10010];

int serch(int n){

    if(n==3){

        return 5;

    }

    if(n==2){

        return 3;

    }

    if(n==1){

        return 1;

    }

    if(dt[n]!=-1)

        return dt[n];

    return dt[n]=(serch(n-1)+serch(n-2)+serch(n-2))%100007;

}

int main()

{

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

    int N;

    scanf("%d",&N);

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

    return 0;

}