import java.util.HashMap;
import java.util.Map;

public class Euler539 {
    private static final long MOD = 987654321L;

    private static long modAdd(long a, long b) {
        long s = (a % MOD + b % MOD) % MOD;
        if (s < 0)
            s += MOD;
        return s;
    }

    private static long modSub(long a, long b) {
        long s = (a % MOD - b % MOD) % MOD;
        if (s < 0)
            s += MOD;
        return s;
    }

    private static long modMul(long a, long b) {
        long s = ((a % MOD) * (b % MOD)) % MOD;
        if (s < 0)
            s += MOD;
        return s;
    }

    private static Map<Long, Long> memoP = new HashMap<>();
    private static Map<Long, Long> memoS = new HashMap<>();

    private static long P(long n) {
        if (n <= 1)
            return 1;
        if (memoP.containsKey(n))
            return memoP.get(n);
        long m = n / 2;
        long pm = P(m);
        long res = 2 * (1 + m - pm);
        memoP.put(n, res);
        return res;
    }

    private static long S(long n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1 % MOD;
        if (memoS.containsKey(n))
            return memoS.get(n);

        long m = n / 2;
        long Sm = S(m);

        long res;
        if ((n & 1) != 0) {
            long term = modMul(2, modMul(m, m + 3));
            long sub4 = modMul(4, Sm);
            res = modAdd(1, modSub(term, sub4));
        } else {
            long mmod = m % MOD;
            long term2m2 = modMul(2, modMul(mmod, mmod));
            long term4m = modMul(4, mmod);
            long base = modSub(modAdd(term2m2, term4m), 1);
            long sub4 = modMul(4, Sm);
            long add2P = modMul(2, P(m) % MOD);
            res = modAdd(modSub(base, sub4), add2P);
        }

        memoS.put(n, res);
        return res;
    }

    public static void main(String[] args) {
        long ans = S(1000000000000000000L) % MOD;
        if (ans < 0)
            ans += MOD;
        System.out.println(ans);
    }
}