import java.util.*;

public class Euler78 {
    public static void main(String[] args) {
        int MOD = 1000000;
        List<Integer> p = new ArrayList<>();
        p.add(1);
        for (int n = 1;; n++) {
            long val = 0;
            for (int k = 1;; k++) {
                int g1 = k * (3 * k - 1) / 2, g2 = k * (3 * k + 1) / 2;
                if (g1 > n)
                    break;
                int sign = k % 2 == 1 ? 1 : -1;
                val += sign * p.get(n - g1);
                if (g2 <= n)
                    val += sign * p.get(n - g2);
            }
            int modded = (int) (val % MOD);
            if (modded < 0)
                modded += MOD;
            p.add(modded);
            if (modded == 0) {
                System.out.println(n);
                return;
            }
        }
    }
}