import java.util.*;

public class Euler326 {
    public static String solve() {
        long limitN = 1000000000000L;
        int mVal = 1000000;

        long period = 6L * mVal;
        long fullCycles = limitN / period;
        long remainder = limitN % period;

        long[] freqInPeriod = new long[mVal];
        long[] freqInTail = new long[mVal];

        long sumLow = 0;
        long sumHigh = 0;
        int prefixMod = 0;

        for (long n = 0; n < period; n++) {
            freqInPeriod[prefixMod]++;
            if (n <= remainder) {
                freqInTail[prefixMod]++;
            }

            long idx = n + 1;
            long a;
            if (idx == 1) {
                a = 1;
            } else {
                long r64 = (Long.remainderUnsigned(-1L, idx) + 1) % idx;
                long hMod = Long.remainderUnsigned(sumHigh, idx);
                long lMod = Long.remainderUnsigned(sumLow, idx);
                a = (hMod * r64 + lMod) % idx;
            }

            long val = idx * a;
            sumLow += val;
            if (Long.compareUnsigned(sumLow, val) < 0) {
                sumHigh++;
            }

            prefixMod = (int) ((prefixMod + a % mVal) % mVal);
        }

        // Java 128 bit answer... wait!
        // answer can be (6,000,000)^2 / 2 ~ 1.8 * 10^13 ? No!
        // max value of answer:
        // sum_r (count_r * count_r / 2)
        // count_r is full_cycles * freq_in_period + freq_in_tail
        // fullCycles = 10^12 / 6M = 166,666.
        // sum(freq) = 6,000,000.
        // So sum(count) = 10^12.
        // answer is at worst 10^12 * 10^12 / 2 = 5 * 10^{23}.
        // This EXCEEDS Long.MAX_VALUE ~ 9 * 10^{18}.
        // We MUST use BigInteger for the final answer accumulation!

        java.math.BigInteger answer = java.math.BigInteger.ZERO;

        java.math.BigInteger fcBig = java.math.BigInteger.valueOf(fullCycles);

        for (int r = 0; r < mVal; r++) {
            java.math.BigInteger count = fcBig.multiply(java.math.BigInteger.valueOf(freqInPeriod[r]))
                    .add(java.math.BigInteger.valueOf(freqInTail[r]));
            java.math.BigInteger terms = count.multiply(count.subtract(java.math.BigInteger.ONE))
                    .divide(java.math.BigInteger.valueOf(2));
            answer = answer.add(terms);
        }

        return answer.toString();
    }

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