import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Euler488 {

    private static final long MOD = 1_000_000_000L;

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

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

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

    private static long sumLinearMod(long m) {
        if (m == 0)
            return 0;
        long a = m, b = m + 1;
        if ((a & 1) == 0)
            a >>= 1;
        else
            b >>= 1;
        return mulMod(a, b);
    }

    private static long sumSquareMod(long m) {
        if (m == 0)
            return 0;
        long a = m, b = m + 1, c = 2 * m + 1;
        if ((a & 1) == 0)
            a >>= 1;
        else if ((b & 1) == 0)
            b >>= 1;
        else
            c >>= 1;

        if (a % 3 == 0)
            a /= 3;
        else if (b % 3 == 0)
            b /= 3;
        else
            c /= 3;

        return mulMod(mulMod(a, b), c);
    }

    private static long sumChoose2Mod(long m) {
        if (m <= 1)
            return 0;
        long a = m, b = m + 1, c = m - 1;
        if ((a & 1) == 0)
            a >>= 1;
        else if ((b & 1) == 0)
            b >>= 1;
        else
            c >>= 1;

        if (a % 3 == 0)
            a /= 3;
        else if (b % 3 == 0)
            b /= 3;
        else
            c /= 3;

        return mulMod(mulMod(a, b), c);
    }

    static class Block {
        long p, m;

        Block(long p, long m) {
            this.p = p;
            this.m = m;
        }
    }

    static class Solver {
        long[] sPow2Mod = new long[63];
        long[] cMod = new long[63];

        Solver() {
            precomputePrefixXorSums();
        }

        private void precomputePrefixXorSums() {
            for (int m = 0; m <= 62; ++m) {
                long p = 1L << m;
                long x = p;
                long y = 3L * p - 1L;
                if ((x & 1L) == 0)
                    x >>= 1;
                else
                    y >>= 1;
                cMod[m] = mulMod(x, y);
            }
            for (int m = 0; m < 62; ++m) {
                long p = (1L << m) % MOD;
                long term = mulMod(p, cMod[m]);
                sPow2Mod[m + 1] = addMod(addMod(sPow2Mod[m], sPow2Mod[m]), term);
            }
        }

        long prefixSumXMod(long n) {
            if (n <= 1)
                return 0;
            int msb = 63 - Long.numberOfLeadingZeros(n);
            long p = 1L << msb;
            if (n == p)
                return sPow2Mod[msb];
            long r = n - p;
            long term = mulMod(r % MOD, cMod[msb]);
            return addMod(addMod(sPow2Mod[msb], term), prefixSumXMod(r));
        }

        long blockSumMod(long p, long m) {
            long sX = prefixSumXMod(m + 1);
            long s1 = sumLinearMod(m);
            long s2 = sumSquareMod(m);
            long sC2 = sumChoose2Mod(m);

            long twoPMinusOne = (2L * (p % MOD) - 1L) % MOD;
            if (twoPMinusOne < 0)
                twoPMinusOne += MOD;

            long total = 0;
            total = addMod(total, sX);
            total = addMod(total, s2);
            total = addMod(total, sC2);
            total = addMod(total, mulMod(twoPMinusOne, s1));

            long oddCnt = (m + 1L) >> 1;
            long oddSq = mulMod(oddCnt % MOD, oddCnt % MOD);
            long correction = addMod(mulMod(oddCnt % MOD, twoPMinusOne), mulMod(2L, oddSq));

            return subMod(total, correction);
        }

        long solveMod(long N, boolean allowMultithreading) throws InterruptedException, ExecutionException {
            List<Block> blocks = new ArrayList<>();
            for (int k = 1; k <= 62; ++k) {
                long p = (1L << k) - 1L;
                if (p + 1L >= N)
                    break;
                long m = Math.min(p, N - 1L - p);
                blocks.add(new Block(p, m));
            }

            if (blocks.isEmpty())
                return 0;

            int workers = 1;
            if (allowMultithreading) {
                int hw = Runtime.getRuntime().availableProcessors();
                if (hw > 0)
                    workers = Math.min(hw, blocks.size());
                if (blocks.size() < 8)
                    workers = 1;
            }

            if (workers == 1) {
                long ans = 0;
                for (Block blk : blocks) {
                    ans = addMod(ans, blockSumMod(blk.p, blk.m));
                }
                return ans;
            }

            ExecutorService executor = Executors.newFixedThreadPool(workers);
            List<Future<Long>> futures = new ArrayList<>();

            for (int tid = 0; tid < workers; ++tid) {
                final int currentTid = tid;
                final int finalWorkers = workers;
                futures.add(executor.submit(() -> {
                    int L = blocks.size() * currentTid / finalWorkers;
                    int R = blocks.size() * (currentTid + 1) / finalWorkers;
                    long local = 0;
                    for (int i = L; i < R; ++i) {
                        local = addMod(local, blockSumMod(blocks.get(i).p, blocks.get(i).m));
                    }
                    return local;
                }));
            }

            long ans = 0;
            for (Future<Long> f : futures) {
                ans = addMod(ans, f.get());
            }
            executor.shutdown();
            return ans;
        }
    }

    public static void main(String[] args) throws Exception {
        Solver solver = new Solver();
        long ans = solver.solveMod(1_000_000_000_000_000_000L, true);
        System.out.printf("%09d\n", ans);
    }
}