public class Euler374 {
    static final long kMod = 982451653L;

    static long isqrt(long n) {
        long approx = (long) Math.sqrt(n);
        while ((approx + 1) <= n / (approx + 1))
            approx++;
        while (approx > n / approx)
            approx--;
        return approx;
    }

    static long maxMForN(long n) {
        long m = (isqrt(8 * n + 9) - 3) / 2;
        while ((m + 1) * (m + 4) / 2 <= n)
            m++;
        while (m > 0 && m * (m + 3) / 2 > n)
            m--;
        return m;
    }

    static String solve() {
        long n = 100000000000000L;
        if (n == 0)
            return "0";

        long answer = 1;

        long mMax = maxMForN(n);
        int invLimit = (int) (mMax + 3);

        int[] inv = new int[invLimit + 1];
        inv[1] = 1;
        for (int i = 2; i <= invLimit; i++) {
            inv[i] = (int) ((kMod - (kMod / i) * inv[(int) (kMod % i)] % kMod) % kMod);
        }

        long inv2 = (kMod + 1) / 2;

        long fact = 1;
        long harmonic = 0;
        int upto = 1;

        for (long m = 1; m <= mMax; m++) {
            long target = m + 2;
            while (upto < target) {
                upto++;
                fact = (fact * upto) % kMod;
                if (upto >= 2) {
                    harmonic = (harmonic + inv[upto]) % kMod;
                }
            }

            long start = m * (m + 3) / 2;
            long endFull = (m + 1) * (m + 4) / 2 - 1;
            long len = Math.min(n, endFull) - start + 1;

            long mm = m % kMod;
            long base = (mm * fact) % kMod;

            long add = 0;
            if (len <= m) {
                int d1 = (int) (m + 3 - len);
                int d2 = (int) (m + 2);
                long partialH = 0;
                for (int d = d1; d <= d2; d++) {
                    partialH += inv[d];
                }
                partialH %= kMod;
                add = (base * partialH) % kMod;
            } else if (len == m + 1) {
                add = (base * harmonic) % kMod;
            } else {
                add = (base * harmonic) % kMod;
                long factM3 = (fact * (m + 3)) % kMod;
                long extra = (mm * factM3) % kMod;
                extra = (extra * inv2) % kMod;
                extra = (extra * inv[(int) (m + 2)]) % kMod;
                add = (add + extra) % kMod;
            }

            answer = (answer + add) % kMod;
        }

        return Long.toString(answer);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}