import java.math.BigInteger;

public class Euler472 {

    private static final long MOD = 100_000_000L;

    private static class Precomp {
        BigInteger[] blockSum = new BigInteger[64];
        BigInteger[] blockPref3q = new BigInteger[64];
        BigInteger[] powPrefix = new BigInteger[64];
        long[][] baseBlocks = new long[5][];
        BigInteger[][] basePref = new BigInteger[5][];

        public Precomp() {
            for (int i = 0; i < 64; i++) {
                blockSum[i] = BigInteger.ZERO;
                blockPref3q[i] = BigInteger.ZERO;
                powPrefix[i] = BigInteger.ZERO;
            }
        }
    }

    private static BigInteger b(long v) {
        return BigInteger.valueOf(v);
    }

    private static BigInteger prefixR(long r, long m) {
        if (m == 0)
            return BigInteger.ZERO;
        if (m == 1)
            return b(4 * r + 2);
        long t = m - 1;
        BigInteger p1 = b(4 * r + 2);
        BigInteger p2 = b(t).multiply(b(2 * r - m + 2));
        return p1.add(p2);
    }

    private static BigInteger sumR(long r) {
        return b(r).multiply(b(r + 5));
    }

    private static BigInteger prefixS(long m) {
        return b(m).multiply(b(m + 1));
    }

    private static BigInteger sumS(long r) {
        BigInteger rr = b(r).multiply(b(r));
        return rr.multiply(b(4)).add(b(2 * r));
    }

    private static BigInteger prefixU(long r, long m) {
        if (m == 0)
            return BigInteger.ZERO;
        if (m == 1)
            return b(6 * r + 3);
        long t = m - 1;
        BigInteger p1 = b(6 * r + 3);
        BigInteger p2 = b(t).multiply(b(4 * r - m + 6)).divide(b(2));
        return p1.add(p2);
    }

    private static BigInteger sumU(long r) {
        BigInteger rr = b(r).multiply(b(r));
        return rr.multiply(b(2)).add(b(11 * r));
    }

    private static Precomp buildPrecomp() {
        Precomp pc = new Precomp();
        pc.baseBlocks[0] = new long[] { 2 };
        pc.baseBlocks[1] = new long[] { 2, 4 };
        pc.baseBlocks[2] = new long[] { 3, 6, 2, 6 };
        pc.baseBlocks[3] = new long[] { 3, 8, 2, 6, 2, 4, 9, 4 };
        pc.baseBlocks[4] = new long[] { 3, 8, 2, 6, 2, 4, 10, 4, 2, 4, 6, 8, 15, 6, 5, 4 };

        for (int k = 0; k <= 4; ++k) {
            long[] blk = pc.baseBlocks[k];
            pc.basePref[k] = new BigInteger[blk.length + 1];
            pc.basePref[k][0] = BigInteger.ZERO;
            for (int i = 0; i < blk.length; ++i) {
                pc.basePref[k][i + 1] = pc.basePref[k][i].add(b(blk[i]));
            }
            pc.blockSum[k] = pc.basePref[k][blk.length];

            int firstThreeQuarters = (3 * (1 << k)) / 4;
            pc.blockPref3q[k] = pc.basePref[k][firstThreeQuarters];
        }

        for (int k = 5; k < 64; ++k) {
            long r = 1L << (k - 3);
            BigInteger rr = b(r).multiply(b(r));
            pc.blockPref3q[k] = pc.blockPref3q[k - 1].add(b(5).multiply(rr)).add(b(7 * r));
            pc.blockSum[k] = pc.blockPref3q[k].add(b(2).multiply(rr)).add(b(11 * r));
        }

        pc.powPrefix[0] = BigInteger.ONE;
        for (int k = 1; k < 64; ++k) {
            pc.powPrefix[k] = pc.powPrefix[k - 1].add(pc.blockSum[k - 1]);
        }
        return pc;
    }

    private static BigInteger blockPrefixSum(Precomp pc, int k, long m) {
        if (m == 0)
            return BigInteger.ZERO;
        long len = 1L << k;
        if (m >= len)
            return pc.blockSum[k];

        if (k <= 4) {
            return pc.basePref[k][(int) m];
        }

        long q = 3L * (1L << (k - 3));
        long r = 1L << (k - 3);
        long s = 1L << (k - 2);

        if (m <= q) {
            return blockPrefixSum(pc, k - 1, m);
        }
        if (m <= q + r) {
            return pc.blockPref3q[k - 1].add(prefixR(r, m - q));
        }
        if (m <= q + r + s) {
            return pc.blockPref3q[k - 1].add(sumR(r)).add(prefixS(m - q - r));
        }
        return pc.blockPref3q[k - 1].add(sumR(r)).add(sumS(r)).add(prefixU(r, m - q - r - s));
    }

    private static BigInteger prefixSum(Precomp pc, long n) {
        if (n == 0)
            return BigInteger.ZERO;
        if (n == 1)
            return BigInteger.ONE;

        int k = 63 - Long.numberOfLeadingZeros(n);
        long p = 1L << k;
        BigInteger out = pc.powPrefix[k];
        if (n > p) {
            out = out.add(blockPrefixSum(pc, k, n - p));
        }
        return out;
    }

    public static void main(String[] args) {
        long n = 1_000_000_000_000L;
        Precomp pc = buildPrecomp();
        BigInteger total = prefixSum(pc, n);
        long answer = total.remainder(b(MOD)).longValue();
        System.out.printf("%08d%n", answer);
    }
}