/*NowCoder号称自己已经记住了1 - 100000之间所有的斐波那契数。
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。
*/
#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n;
    vector<int>fib(100001, 0);
    //计算1-100000的斐波那契数并存放到fib中
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < fib.size(); i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
        fib[i] = fib[i] % 1000000;
    }
    while (cin >> n) {
        //输出时考虑斐波那契数后六位以0开头的数，因此以%06d输出位数超过六位的后六位数
        printf(n < 29 ? "%d\n" : "%06d\n", fib[n]);
    }
    return 0;
}