1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 typedef long long ll;
 7 #define MS(a) memset(a,0,sizeof(a))
 8 #define MP make_pair
 9 #define PB push_back
10 const int INF = 0x3f3f3f3f;
11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
12 inline ll read(){
13     ll x=0,f=1;char ch=getchar();
14     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
15     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
16     return x*f;
17 }
18 //////////////////////////////////////////////////////////////////////////
19 const int maxn = 1e5+10;
20 const int mod = 10000;
21 
22 struct mat{
23     int at[2][2];
24 };
25 
26 mat d;
27 int n;
28 
29 mat mul(mat a,mat b){
30     mat re;
31     memset(re.at,0,sizeof(re.at));
32     for(int i=0; i<n; i++)
33         for(int k=0; k<n; k++)
34             for(int j=0; j<n; j++)
35                 re.at[i][j] = (re.at[i][j]+a.at[i][k]*b.at[k][j])%mod;
36         
37     return re;
38 }
39 
40 mat expo(mat p,int k){
41     if(k == 1) return p;
42     mat e;
43     memset(e.at,0,sizeof(e.at));
44     for(int i=0; i<n; i++) { e.at[i][i]=1; }
45     if(k == 0) return e;
46     while(k){
47         if(k&1) e = mul(p,e);
48         p = mul(p,p);
49         k >>= 1;
50     }
51     return e;
52 }
53 
54 int main(){
55     n = 2;
56     d.at[1][1] = 0;
57     d.at[0][0]=d.at[0][1]=d.at[1][0] = 1;
58     int k;
59     while(cin >> k){
60         if(k == -1) break;
61         mat res = expo(d,k);
62         int ans = res.at[1][0]%mod;
63         cout << ans << endl;
64     }
65 
66     return 0;
67 }