#include<iostream>

 #include<stdio.h>

 using namespace std;

 const int mod = ;

 struct mat{

     int m[][];

 };

 mat operator * (mat a, mat b){        //重载乘号，同时将数据mod10000

     mat ret;

     for(int i = ; i < ; i++){

         for(int j = ; j < ; j++){

             long long temp = ;

             for(int k = ; k < ; k++){

                 temp += a.m[i][k] * b.m[k][j];

                 temp %= mod;

             }

             ret.m[i][j] = temp;

         }

     }

     return ret;

 }

 mat pow_mat(mat a, int n){        //矩阵快速幂和快速幂相同（广义快速幂的思想）

     mat res = a;

     while(n){

         if(n&) res = res * a;

         a = a*a;

         n >>= ;

     }

     return res;

 }

 int main(){

     int n;

     while(scanf("%d", &n) !=EOF){

         if(n == -) break;

         if(n == ) printf("0\n");

         else if(n == ) printf("1\n");

         else if(n == ) printf("1\n");

         else{

             mat a;                            //构造一个初始的矩阵 其n-2次方的m[0][0]就是所求的答案

             a.m[][] = ;

             a.m[][] = ;

             a.m[][] = ;

             a.m[][] = ;

             mat ans = pow_mat(a, n-);        //调用矩阵快速幂计算

             printf("%d\n", ans.m[][]);

         }

     }

     return ;

 }