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

public class Euler702 {
    static class Key {
        long x, m;

        Key(long x, long m) {
            this.x = x;
            this.m = m;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Key key = (Key) o;
            return x == key.x && m == key.m;
        }

        @Override
        public int hashCode() {
            int result = Long.hashCode(x);
            result = 31 * result + Long.hashCode(m);
            return result;
        }
    }

    static Map<Key, Long> cache = new HashMap<>();

    static long f(long x, long m) {
        x %= m;
        if (x <= 1)
            return 0;

        Key key = new Key(x, m);
        if (cache.containsKey(key))
            return cache.get(key);

        long t = m / x;
        long y = m % x;

        BigInteger biT = BigInteger.valueOf(t);
        BigInteger biX = BigInteger.valueOf(x);

        BigInteger termBi = biT.multiply(biT.add(BigInteger.ONE))
                .multiply(biX)
                .multiply(biX.subtract(BigInteger.ONE))
                .divide(BigInteger.valueOf(4));
        long term = termBi.longValue();

        long res = term + (t + 1) * f(x, y) - t * f(x, x - y);

        cache.put(key, res);
        return res;
    }

    static long g(long x, long m) {
        return (m - 1) * (m - 2) - f(x, m);
    }

    public static String solve() {
        cache.clear();
        long n = 123456789L;

        int D = 0;
        long temp = n;
        while (temp > 0) {
            D++;
            temp >>= 1;
        }

        BigInteger biN = BigInteger.valueOf(n);
        BigInteger part1 = biN.multiply(biN.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE))
                .divide(BigInteger.valueOf(2));
        BigInteger ansBi = part1.multiply(BigInteger.valueOf(D + 1));
        long ans = ansBi.longValue();

        for (int d = 2; d <= D; ++d) {
            ans -= g(n, 1L << d);
        }
        ans += 2 * g(n, (1L << D) - n);

        return Long.toString(ans);
    }

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