public class Euler509 {
    private static final long MOD = 1234567890L;

    private static long[] valuationCounts(long n) {
        long[] count = new long[64];
        for (int k = 0; k < 63; ++k) {
            long a = n >> k;
            if (a == 0)
                break;
            long b = n >> (k + 1);
            count[k] = a - b;
        }
        return count;
    }

    public static void main(String[] args) {
        long n = 123456787654321L;
        long[] count = valuationCounts(n);

        long losingMod = 0;
        for (int i = 0; i < 64; ++i) {
            if (count[i] == 0)
                continue;
            for (int j = 0; j < 64; ++j) {
                if (count[j] == 0)
                    continue;
                int k = i ^ j;
                if (k >= 64 || count[k] == 0)
                    continue;

                long term = ((count[i] % MOD) * (count[j] % MOD)) % MOD;
                term = (term * (count[k] % MOD)) % MOD;
                losingMod = (losingMod + term) % MOD;
            }
        }

        long nMod = n % MOD;
        long totalMod = (((nMod * nMod) % MOD) * nMod) % MOD;
        long res = (totalMod + MOD - losingMod) % MOD;
        System.out.println(res);
    }
}