#include <iostream>
using namespace std;
void fib(unsigned long n)
{
unsigned long long a = 1, b = 1;
for (unsigned long i = 1; i < n; i++) {
b = a + b; //pod zmienną b przypisujemy wyraz następny czyli a+b
a = b - a;
b = b % 10000;
a = a % 10000;
}
cout << a;
}
int main()
{
unsigned long n;
cin >> n;
fib(n);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKdm9pZCBmaWIodW5zaWduZWQgbG9uZyBuKQp7CiAgICB1bnNpZ25lZCBsb25nIGxvbmcgYSA9IDEsIGIgPSAxOwogICAgZm9yICh1bnNpZ25lZCBsb25nIGkgPSAxOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgYiA9IGEgKyBiOyAvL3BvZCB6bWllbm7EhSBiIHByenlwaXN1amVteSB3eXJheiBuYXN0xJlwbnkgY3p5bGkgYStiCiAgICAgICAgYSA9IGIgLSBhOwogICAgICAgIGIgPSBiICUgMTAwMDA7CiAgICAgICAgYSA9IGEgJSAxMDAwMDsKICAgIH0KICAgIGNvdXQgPDwgYTsKfQogCmludCBtYWluKCkKewogICAgdW5zaWduZWQgbG9uZyBuOwogICAgY2luID4+IG47CiAgICBmaWIobik7CiAgICByZXR1cm4gMDsKfQ==