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

public class Euler520 {

    static final long MOD = 1000000123L;

    static long modPow(long base, long exp) {
        long result = 1L;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }

    static long modInverse(long x) {
        return modPow(x % MOD, MOD - 2);
    }

    static long geomSumFromOne(long lambda, long n) {
        if (n == 0)
            return 0;
        if (lambda == 1)
            return n % MOD;
        if (lambda == 0)
            return 0;

        long lm = (lambda % MOD + MOD) % MOD;
        long num = (lm * ((modPow(lm, n) + MOD - 1) % MOD)) % MOD;
        long den = (lm + MOD - 1) % MOD;
        return (num * modInverse(den)) % MOD;
    }

    static long geomSumFromZero(long lambda, long n) {
        if (n == 0)
            return 0;
        if (lambda == 1)
            return n % MOD;
        if (lambda == 0)
            return 1;

        long lm = (lambda % MOD + MOD) % MOD;
        long num = (modPow(lm, n) + MOD - 1) % MOD;
        long den = (lm + MOD - 1) % MOD;
        return (num * modInverse(den)) % MOD;
    }

    static class Pair {
        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair pair = (Pair) o;
            return a == pair.a && b == pair.b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }
    }

    static Map<Long, Long> expandCoeffsF() {
        Map<Pair, Long> poly1 = new HashMap<>();
        poly1.put(new Pair(0, 0), 1L);
        int[][] base1 = { { 0, 0, 2 }, { 1, 0, 1 }, { 0, 1, -1 } };

        for (int rep = 0; rep < 5; rep++) {
            Map<Pair, Long> next = new HashMap<>();
            for (Map.Entry<Pair, Long> e : poly1.entrySet()) {
                for (int[] term : base1) {
                    Pair nk = new Pair(e.getKey().a + term[0], e.getKey().b + term[1]);
                    next.put(nk, next.getOrDefault(nk, 0L) + e.getValue() * term[2]);
                }
            }
            poly1 = next;
        }

        Map<Pair, Long> poly2 = new HashMap<>();
        poly2.put(new Pair(0, 0), 1L);
        int[][] base2 = { { 1, 0, 1 }, { 0, 1, 1 } };

        for (int rep = 0; rep < 5; rep++) {
            Map<Pair, Long> next = new HashMap<>();
            for (Map.Entry<Pair, Long> e : poly2.entrySet()) {
                for (int[] term : base2) {
                    Pair nk = new Pair(e.getKey().a + term[0], e.getKey().b + term[1]);
                    next.put(nk, next.getOrDefault(nk, 0L) + e.getValue() * term[2]);
                }
            }
            poly2 = next;
        }

        Map<Pair, Long> both = new HashMap<>();
        for (Map.Entry<Pair, Long> a : poly1.entrySet()) {
            for (Map.Entry<Pair, Long> b : poly2.entrySet()) {
                Pair nk = new Pair(a.getKey().a + b.getKey().a, a.getKey().b + b.getKey().b);
                both.put(nk, both.getOrDefault(nk, 0L) + a.getValue() * b.getValue());
            }
        }

        Map<Long, Long> byLambda = new HashMap<>();
        for (Map.Entry<Pair, Long> row : both.entrySet()) {
            long lam = row.getKey().a - row.getKey().b;
            byLambda.put(lam, byLambda.getOrDefault(lam, 0L) + row.getValue());
        }
        return byLambda;
    }

    static Map<Long, Long> expandCoeffsG() {
        Map<Pair, Long> poly1 = new HashMap<>();
        poly1.put(new Pair(0, 0), 1L);
        int[][] base1 = { { 0, 0, 2 }, { 1, 0, 1 }, { 0, 1, -1 } };

        for (int rep = 0; rep < 5; rep++) {
            Map<Pair, Long> next = new HashMap<>();
            for (Map.Entry<Pair, Long> e : poly1.entrySet()) {
                for (int[] term : base1) {
                    Pair nk = new Pair(e.getKey().a + term[0], e.getKey().b + term[1]);
                    next.put(nk, next.getOrDefault(nk, 0L) + e.getValue() * term[2]);
                }
            }
            poly1 = next;
        }

        Map<Pair, Long> poly2 = new HashMap<>();
        poly2.put(new Pair(0, 0), 1L);
        int[][] base2 = { { 1, 0, 1 }, { 0, 1, 1 } };

        for (int rep = 0; rep < 4; rep++) {
            Map<Pair, Long> next = new HashMap<>();
            for (Map.Entry<Pair, Long> e : poly2.entrySet()) {
                for (int[] term : base2) {
                    Pair nk = new Pair(e.getKey().a + term[0], e.getKey().b + term[1]);
                    next.put(nk, next.getOrDefault(nk, 0L) + e.getValue() * term[2]);
                }
            }
            poly2 = next;
        }

        Map<Pair, Long> diff = new HashMap<>();
        diff.put(new Pair(1, 0), 1L);
        diff.put(new Pair(0, 1), -1L);

        Map<Pair, Long> tmp = new HashMap<>();
        for (Map.Entry<Pair, Long> a : poly1.entrySet()) {
            for (Map.Entry<Pair, Long> b : poly2.entrySet()) {
                Pair nk = new Pair(a.getKey().a + b.getKey().a, a.getKey().b + b.getKey().b);
                tmp.put(nk, tmp.getOrDefault(nk, 0L) + a.getValue() * b.getValue());
            }
        }

        Map<Pair, Long> both = new HashMap<>();
        for (Map.Entry<Pair, Long> a : tmp.entrySet()) {
            for (Map.Entry<Pair, Long> b : diff.entrySet()) {
                Pair nk = new Pair(a.getKey().a + b.getKey().a, a.getKey().b + b.getKey().b);
                both.put(nk, both.getOrDefault(nk, 0L) + a.getValue() * b.getValue());
            }
        }

        Map<Long, Long> byLambda = new HashMap<>();
        for (Map.Entry<Pair, Long> row : both.entrySet()) {
            long lam = row.getKey().a - row.getKey().b;
            byLambda.put(lam, byLambda.getOrDefault(lam, 0L) + row.getValue());
        }
        return byLambda;
    }

    static long Q(long n, Map<Long, Long> cf, Map<Long, Long> cg, long invTwoPow10) {
        long sumA = 0;
        for (Map.Entry<Long, Long> entry : cf.entrySet()) {
            long geom = geomSumFromOne(entry.getKey(), n);
            long coeffMod = (entry.getValue() % MOD + MOD) % MOD;
            sumA = (sumA + (coeffMod * geom) % MOD) % MOD;
        }

        long sumB = 0;
        for (Map.Entry<Long, Long> entry : cg.entrySet()) {
            long geom = geomSumFromZero(entry.getKey(), n);
            long coeffMod = (entry.getValue() % MOD + MOD) % MOD;
            sumB = (sumB + (coeffMod * geom) % MOD) % MOD;
        }

        return (((sumA + MOD - sumB) % MOD) * invTwoPow10) % MOD;
    }

    public static void main(String[] args) {
        int maxPower = 39;
        Map<Long, Long> cf = expandCoeffsF();
        Map<Long, Long> cg = expandCoeffsG();
        long invTwoPow10 = modInverse(1024L);

        long ans = 0;
        for (int u = 1; u <= maxPower; u++) {
            long n = 1L << u;
            ans += Q(n, cf, cg, invTwoPow10);
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
        System.out.println(ans);
    }
}