public class Euler944 {
    static final long kMod = 1234567891L;
    static final long kSplit = 3000000L;

    static long addMod(long a, long b) {
        a += b;
        if (a >= kMod) {
            a -= kMod;
        }
        return a;
    }

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

    static long mulMod(long a, long b) {
        return (a * b) % kMod;
    }

    static long powMod(long base, long exp) {
        long result = 1 % kMod;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = mulMod(result, base);
            }
            base = mulMod(base, base);
            exp >>= 1;
        }
        return result;
    }

    static long sumRangeMod(long l, long r) {
        if (l > r) {
            return 0;
        }
        long cnt = (r - l + 1) % kMod;
        long s = (l + r) % kMod;
        long total = (cnt * s) % kMod;
        long inv2 = (kMod + 1L) / 2L;
        return (total * inv2) % kMod;
    }

    public static String solve(long n) {
        long powNMinus1 = powMod(2, n - 1);
        long split = Math.min(n, kSplit);

        long weightedSum = 0;

        for (long x = 1; x <= split; ++x) {
            long q = n / x;
            long p = powMod(2, n - q);
            weightedSum = addMod(weightedSum, mulMod(x % kMod, p));
        }

        long inv2 = (kMod + 1L) / 2L;
        long qmax = n / (split + 1L);
        long p = powNMinus1;

        for (long q = 1; q <= qmax; ++q) {
            long l = n / (q + 1L) + 1L;
            if (l <= split) {
                l = split + 1L;
            }
            long r = n / q;
            if (l <= r) {
                long sumX = sumRangeMod(l, r);
                weightedSum = addMod(weightedSum, mulMod(sumX, p));
            }
            p = mulMod(p, inv2);
        }

        long tri = sumRangeMod(1, n);
        long first = mulMod(powNMinus1, tri);
        return Long.toString(subMod(first, weightedSum));
    }

    public static void main(String[] args) {
        if (!solve(1).equals("0") || !solve(10).equals("4927")) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve(100000000000000L));
    }
}