import java.math.BigInteger;

public class Euler325 {
    static final long TARGET_N = 10000000000000000L;
    static final long MOD = 282475249L;

    static long floorDivPhi(long n) {
        if (n == 0)
            return 0;
        BigInteger nn = BigInteger.valueOf(n);
        BigInteger radicand = BigInteger.valueOf(5).multiply(nn).multiply(nn);
        BigInteger floorNSqrt5 = radicand.sqrt();
        return floorNSqrt5.subtract(nn).divide(BigInteger.valueOf(2)).longValue();
    }

    static long modAdd(long a, long b, long m) {
        return (a + b) % m;
    }

    static long modSub(long a, long b, long m) {
        return (a >= b) ? (a - b) : (a + m - b);
    }

    static long modMul(long a, long b, long m) {
        return (a * b) % m;
    }

    static long modPow(long base, long exp, long m) {
        long res = 1;
        base %= m;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = modMul(res, base, m);
            base = modMul(base, base, m);
            exp >>= 1;
        }
        return res;
    }

    static long triangularMod(long n, long m, long inv2) {
        return modMul(modMul(n % m, (n + 1) % m, m), inv2, m);
    }

    static long squareSumMod(long n, long m, long inv6) {
        long a = n % m;
        long b = (n + 1) % m;
        long c = (2 * a + 1) % m;
        return modMul(modMul(modMul(a, b, m), c, m), inv6, m);
    }

    static class BeattySums {
        long g, p, q;

        BeattySums(long g, long p, long q) {
            this.g = g;
            this.p = p;
            this.q = q;
        }
    }

    static BeattySums beattySumsMod(long n, long mod, long inv2, long inv6) {
        if (n == 0)
            return new BeattySums(0, 0, 0);

        long m = floorDivPhi(n);
        BeattySums child = beattySumsMod(m, mod, inv2, inv6);

        long nMod = n % mod;
        long mMod = m % mod;
        long triM = triangularMod(m, mod, inv2);
        long sqM = squareSumMod(m, mod, inv6);

        long g = modMul(nMod, mMod, mod);
        g = modSub(g, triM, mod);
        g = modSub(g, child.g, mod);

        long q = modMul(nMod, modMul(mMod, mMod, mod), mod);
        q = modSub(q, modMul(2, sqM, mod), mod);
        q = modSub(q, modMul(2, child.p, mod), mod);
        q = modAdd(q, triM, mod);
        q = modAdd(q, child.g, mod);

        long first = modMul(modMul(nMod, mMod, mod), (n + 1) % mod, mod);
        first = modMul(first, inv2, mod);

        long numerator = sqM;
        numerator = modAdd(numerator, modMul(2, child.p, mod), mod);
        numerator = modAdd(numerator, child.q, mod);
        numerator = modAdd(numerator, triM, mod);
        numerator = modAdd(numerator, child.g, mod);

        long second = modMul(numerator, inv2, mod);
        long p = modSub(first, second, mod);

        return new BeattySums(g, p, q);
    }

    static long solveMod(long n, long mod) {
        BigInteger modBig = BigInteger.valueOf(mod);
        long inv2 = BigInteger.valueOf(2).modInverse(modBig).longValue();
        long inv6 = BigInteger.valueOf(6).modInverse(modBig).longValue();

        long cutoff = floorDivPhi(n + 1);
        BeattySums sums = beattySumsMod(cutoff, mod, inv2, inv6);

        long prefixNum = modMul(4, sums.p, mod);
        prefixNum = modAdd(prefixNum, sums.q, mod);
        prefixNum = modAdd(prefixNum, sums.g, mod);
        long prefix = modMul(prefixNum, inv2, mod);

        if (cutoff == n)
            return prefix;

        long nMod = n % mod;
        long countMod = (n - cutoff) % mod;
        long sumX = modSub(triangularMod(n, mod, inv2), triangularMod(cutoff, mod, inv2), mod);
        long sumX2 = modSub(squareSumMod(n, mod, inv6), squareSumMod(cutoff, mod, inv6), mod);

        long n2PlusN = modAdd(modMul(nMod, nMod, mod), nMod, mod);
        long coeff = modSub(modMul(2, nMod, mod), 1, mod);

        long term1 = modMul(countMod, n2PlusN, mod);
        long term2 = modMul(coeff, sumX, mod);
        long term3 = modMul(3, sumX2, mod);

        long tailNum = modAdd(term1, term2, mod);
        tailNum = modSub(tailNum, term3, mod);
        long tail = modMul(tailNum, inv2, mod);

        return modAdd(prefix, tail, mod);
    }

    public static String solve() {
        return String.valueOf(solveMod(TARGET_N, MOD));
    }

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