#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define MOD 1000000007
#define FOR(i,a,b) for (int i = (a);i <= (b);i++)
#define FOD(i,a,b) for (int i = (b);i >= (a);i--)
#define ALL(x) (x).begin(),(x).end()
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
//const int MOD = 998244353;
const int MAXN = 1e5+7;
ll f[MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    FOR(i,1,1e4){
        f[1] = f[2] = 1;
        int j = 3;
        while((f[j - 1] + f[j - 2]) % 10000 != 0){
            f[j] = f[j - 1] + f[j - 2];
            f[j] = f[j] % 10000;
            j++;
        }
    }
    return (0^0);
}