#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    const int MOD = 1000000;
    vector<int> p;
    p.push_back(1); // p[0] = 1
 
    int n = 1;
    while (true) {
        int sum = 0;
        int i = 0; // Để đếm số hạng k (1, -1, 2, -2...)
 
        while (true) {
            // Sinh k theo thứ tự: 1, -1, 2, -2, 3, -3...
            // i=0 -> k=1; i=1 -> k=-1; i=2 -> k=2...
            int k = (i % 2 == 0) ? (i / 2 + 1) : -(i / 2 + 1);
 
            // Số ngũ giác tổng quát
            int gk = k * (3 * k - 1) / 2;
 
            // Nếu chỉ số vượt quá n thì dừng (không còn quá khứ để tham chiếu)
            if (gk > n) break;
 
            // Xác định dấu: +, +, -, -, +, +...
            // Nhóm 2 số đầu là +, nhóm 2 số sau là -
            // i chạy 0, 1 (k=1, -1) -> Dấu +
            // i chạy 2, 3 (k=2, -2) -> Dấu -
            // i/2 chẵn -> cộng; i/2 lẻ -> trừ
 
            if ((i / 2) % 2 == 0) {
                sum = (sum + p[n - gk]) % MOD;
            } else {
                sum = (sum - p[n - gk]);
                // Xử lý số âm trong modulo
                while (sum < 0) sum += MOD;
                sum %= MOD;
            }
 
            i++;
        }
 
        p.push_back(sum);
 
        // Kiểm tra điều kiện bài toán
        if (sum == 0) {
            cout << "Tim thay n = " << n << endl;
            break;
        }
 
        n++;
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewogICAgY29uc3QgaW50IE1PRCA9IDEwMDAwMDA7CiAgICB2ZWN0b3I8aW50PiBwOwogICAgcC5wdXNoX2JhY2soMSk7IC8vIHBbMF0gPSAxCgogICAgaW50IG4gPSAxOwogICAgd2hpbGUgKHRydWUpIHsKICAgICAgICBpbnQgc3VtID0gMDsKICAgICAgICBpbnQgaSA9IDA7IC8vIMSQ4buDIMSR4bq/bSBz4buRIGjhuqFuZyBrICgxLCAtMSwgMiwgLTIuLi4pCiAgICAgICAgCiAgICAgICAgd2hpbGUgKHRydWUpIHsKICAgICAgICAgICAgLy8gU2luaCBrIHRoZW8gdGjhu6kgdOG7sTogMSwgLTEsIDIsIC0yLCAzLCAtMy4uLgogICAgICAgICAgICAvLyBpPTAgLT4gaz0xOyBpPTEgLT4gaz0tMTsgaT0yIC0+IGs9Mi4uLgogICAgICAgICAgICBpbnQgayA9IChpICUgMiA9PSAwKSA/IChpIC8gMiArIDEpIDogLShpIC8gMiArIDEpOwogICAgICAgICAgICAKICAgICAgICAgICAgLy8gU+G7kSBuZ8WpIGdpw6FjIHThu5VuZyBxdcOhdAogICAgICAgICAgICBpbnQgZ2sgPSBrICogKDMgKiBrIC0gMSkgLyAyOwoKICAgICAgICAgICAgLy8gTuG6v3UgY2jhu4kgc+G7kSB2xrDhu6N0IHF1w6EgbiB0aMOsIGThu6tuZyAoa2jDtG5nIGPDsm4gcXXDoSBraOG7qSDEkeG7gyB0aGFtIGNoaeG6v3UpCiAgICAgICAgICAgIGlmIChnayA+IG4pIGJyZWFrOwoKICAgICAgICAgICAgLy8gWMOhYyDEkeG7i25oIGThuqV1OiArLCArLCAtLCAtLCArLCArLi4uCiAgICAgICAgICAgIC8vIE5ow7NtIDIgc+G7kSDEkeG6p3UgbMOgICssIG5ow7NtIDIgc+G7kSBzYXUgbMOgIC0KICAgICAgICAgICAgLy8gaSBjaOG6oXkgMCwgMSAoaz0xLCAtMSkgLT4gROG6pXUgKwogICAgICAgICAgICAvLyBpIGNo4bqheSAyLCAzIChrPTIsIC0yKSAtPiBE4bqldSAtCiAgICAgICAgICAgIC8vIGkvMiBjaOG6tW4gLT4gY+G7mW5nOyBpLzIgbOG6uyAtPiB0cuG7qwogICAgICAgICAgICAKICAgICAgICAgICAgaWYgKChpIC8gMikgJSAyID09IDApIHsKICAgICAgICAgICAgICAgIHN1bSA9IChzdW0gKyBwW24gLSBna10pICUgTU9EOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgc3VtID0gKHN1bSAtIHBbbiAtIGdrXSk7CiAgICAgICAgICAgICAgICAvLyBY4butIGzDvSBz4buRIMOibSB0cm9uZyBtb2R1bG8KICAgICAgICAgICAgICAgIHdoaWxlIChzdW0gPCAwKSBzdW0gKz0gTU9EOwogICAgICAgICAgICAgICAgc3VtICU9IE1PRDsKICAgICAgICAgICAgfQogICAgICAgICAgICAKICAgICAgICAgICAgaSsrOwogICAgICAgIH0KCiAgICAgICAgcC5wdXNoX2JhY2soc3VtKTsKCiAgICAgICAgLy8gS2nhu4NtIHRyYSDEkWnhu4F1IGtp4buHbiBiw6BpIHRvw6FuCiAgICAgICAgaWYgKHN1bSA9PSAwKSB7CiAgICAgICAgICAgIGNvdXQgPDwgIlRpbSB0aGF5IG4gPSAiIDw8IG4gPDwgZW5kbDsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQoKICAgICAgICBuKys7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K