import java.util.HashMap;
import java.util.Map;
import java.math.BigInteger;

public class Euler535 {
    private static final long kMod = 1000000000L;

    private static long isqrt(long x) {
        long r = (long) Math.sqrt(x);
        while ((r + 1) * (r + 1) <= x) {
            r++;
        }
        while (r * r > x) {
            r--;
        }
        return r;
    }

    private static long sumFloorSqrt(long n) {
        long s = isqrt(n);
        BigInteger bs = BigInteger.valueOf(s);
        BigInteger bs1 = BigInteger.valueOf(s + 1);
        BigInteger b2s1 = BigInteger.valueOf(2 * s + 1);
        BigInteger sumsq = bs.multiply(bs1).multiply(b2s1).divide(BigInteger.valueOf(6));
        BigInteger nn1 = BigInteger.valueOf(n + 1);
        BigInteger res = bs.multiply(nn1).subtract(sumsq);
        return res.longValue();
    }

    private static long triMod(long n) {
        BigInteger bn = BigInteger.valueOf(n);
        BigInteger bn1 = BigInteger.valueOf(n + 1);
        BigInteger t = bn.multiply(bn1).divide(BigInteger.valueOf(2));
        long rem = t.remainder(BigInteger.valueOf(kMod)).longValue();
        if (rem < 0)
            rem += kMod;
        return rem;
    }

    private static Map<Long, Long> memoA = new HashMap<>();
    private static Map<Long, Long> memoU = new HashMap<>();
    private static Map<Long, Long> memoTmod = new HashMap<>();

    static {
        memoA.put(0L, 0L);
        memoU.put(0L, 0L);
        memoTmod.put(0L, 0L);
    }

    private static long U(long k) {
        if (memoU.containsKey(k))
            return memoU.get(k);
        long a = A(k);
        long c = k - a;
        long res = U(a) + sumFloorSqrt(c);
        memoU.put(k, res);
        return res;
    }

    private static long f(long k) {
        return k + U(k);
    }

    private static long A(long n) {
        if (memoA.containsKey(n))
            return memoA.get(n);
        if (n <= 1) {
            memoA.put(n, 0L);
            return 0L;
        }

        long hiMax = n - 1;
        long lo = 0;
        long hi = 1;

        while (hi < hiMax && f(hi) <= n) {
            lo = hi;
            long next = hi << 1;
            hi = (next < hiMax && next > 0) ? next : hiMax;
        }
        if (f(hi) <= n) {
            memoA.put(n, hi);
            return hi;
        }

        while (lo + 1 < hi) {
            long mid = lo + (hi - lo) / 2;
            if (f(mid) <= n) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        memoA.put(n, lo);
        return lo;
    }

    private static long TMod(long n) {
        if (memoTmod.containsKey(n))
            return memoTmod.get(n);
        long a = A(n);
        long c = n - a;
        long res = (TMod(a) + triMod(c)) % kMod;
        memoTmod.put(n, res);
        return res;
    }

    public static void main(String[] args) {
        long n = 1000000000000000000L;
        long ans = TMod(n);
        System.out.printf("%09d\n", ans);
    }
}