#include <iostream>

using namespace std;

int r[1000001] = {1, 1, 2, 3};
int przestaw(int n){
 if (r[n] == 0)
 r[n] = (przestaw(n - 1) + przestaw(n - 2)) % 1000000;
 return r[n];
}
int main()
{
    int n;
    cin >> n;
    if (n <= 1000) cout <<przestaw(n) << endl;
    else {
        for (int i = 4; i <= n; i++)
            r[i] = (r[i - 1] + r[i - 2]) % 1000000;
        cout << r[n] <<endl;
    }
    return 0;
}