import java.math.BigInteger;
import java.util.ArrayList;

public class Euler889 {

    static final long MOD = 1000062031L;

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

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

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

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

    static class FastContext {
        int r;
        long k;
        long t;
        long[] binom;
        long[] binomMod;
        long[] pow2Ti;
        long pow2K;
        long pow2KInv;
        long bMod;
        long[] prefixK;
        long[] suffix;
    }

    static class Task {
        long n;
        int s;

        Task(long n, int s) {
            this.n = n;
            this.s = s;
        }
    }

    static long exceptionContrib(FastContext ctx, long n, int s) {
        long pow2N = modPow(2, n);
        long SMod = 0;

        for (int i = 0; i <= ctx.r; ++i) {
            long base = modMul(ctx.binomMod[i], modMul(pow2N, ctx.pow2Ti[i]));
            if (i < s) {
                SMod = modAdd(SMod, base);
            } else {
                long term = modMul(base, ctx.pow2KInv);
                SMod = modSub(SMod, term);
            }
        }

        int idx = (s <= ctx.r) ? (s - 1) : ctx.r;
        long eMax = n + ctx.t * idx;
        long shift = ctx.k - eMax;
        long CTop = ctx.binom[idx];

        long Q = 0;
        if (shift >= 0 && shift < 63) {
            Q = CTop >>> shift;
        }
        long rMod = modSub(SMod, modMul(Q % MOD, ctx.bMod));

        boolean greater = false;
        if (shift >= 0 && shift < 63) {
            long lowMask = (1L << shift) - 1;
            long low = CTop & lowMask;
            long half = (shift == 0) ? 0 : (1L << (shift - 1));

            if (low < half) {
                greater = false;
            } else if (low > half) {
                greater = true;
            } else {
                greater = (s >= 2);
            }
        }

        long dMod = greater ? modSub(ctx.bMod, rMod) : rMod;
        long pow2KN = modPow(2, ctx.k - n);
        return modMul(dMod, pow2KN);
    }

    static long computeFast(long k, long t, int r) {
        FastContext ctx = new FastContext();
        ctx.r = r;
        ctx.k = k;
        ctx.t = t;
        ctx.binom = new long[r + 1];
        ctx.binomMod = new long[r + 1];
        ctx.pow2Ti = new long[r + 1];
        ctx.prefixK = new long[r + 2];
        ctx.suffix = new long[r + 2];

        ctx.binom[0] = 1;
        BigInteger biNum;
        for (int i = 1; i <= r; ++i) {
            biNum = BigInteger.valueOf(ctx.binom[i - 1]).multiply(BigInteger.valueOf(r - i + 1));
            ctx.binom[i] = biNum.divide(BigInteger.valueOf(i)).longValue();
        }
        for (int i = 0; i <= r; ++i) {
            ctx.binomMod[i] = ctx.binom[i] % MOD;
        }

        long pow2T = modPow(2, t);
        ctx.pow2Ti[0] = 1;
        for (int i = 1; i <= r; ++i) {
            ctx.pow2Ti[i] = modMul(ctx.pow2Ti[i - 1], pow2T);
        }

        ctx.pow2K = modPow(2, k);
        ctx.pow2KInv = modPow(ctx.pow2K, MOD - 2);
        ctx.bMod = modAdd(ctx.pow2K, 1);

        long[] term = new long[r + 1];
        long[] termK = new long[r + 1];
        for (int i = 0; i <= r; ++i) {
            term[i] = modMul(ctx.binomMod[i], ctx.pow2Ti[i]);
            termK[i] = modMul(term[i], ctx.pow2K);
        }

        for (int i = 0; i <= r; ++i) {
            ctx.prefixK[i + 1] = modAdd(ctx.prefixK[i], termK[i]);
        }
        for (int i = r; i >= 0; --i) {
            ctx.suffix[i] = modAdd(ctx.suffix[i + 1], term[i]);
        }

        ArrayList<Task> tasks = new ArrayList<>();
        long[] total = { 0 };

        java.util.function.BiConsumer<Long, Long> addBulk = (bulk, constant) -> {
            if (bulk <= 0)
                return;
            long bulkMod = bulk % MOD;
            total[0] = modAdd(total[0], modMul(bulkMod, constant));
        };

        for (int s = 1; s <= r; ++s) {
            BigInteger startRaw = BigInteger.valueOf(k).subtract(BigInteger.valueOf(s).multiply(BigInteger.valueOf(t)));
            BigInteger endRaw = BigInteger.valueOf(k)
                    .subtract(BigInteger.valueOf(s - 1).multiply(BigInteger.valueOf(t))).subtract(BigInteger.ONE);

            if (endRaw.compareTo(BigInteger.ZERO) < 0)
                continue;

            long start = startRaw.compareTo(BigInteger.ZERO) > 0 ? startRaw.longValue() : 0;
            long end = endRaw.longValue();
            if (end > k - 1)
                end = k - 1;
            if (start > end)
                continue;

            long length = end - start + 1;
            long excStart = Math.max(start, end - 61);
            long excCount = (excStart <= end) ? (end - excStart + 1) : 0;
            long bulk = length - excCount;

            long constant = modSub(ctx.prefixK[s], ctx.suffix[s]);
            addBulk.accept(bulk, constant);

            for (long n = excStart; n <= end; ++n) {
                tasks.add(new Task(n, s));
            }
        }

        int s = r + 1;
        BigInteger endRaw = BigInteger.valueOf(k).subtract(BigInteger.valueOf(r).multiply(BigInteger.valueOf(t)))
                .subtract(BigInteger.ONE);
        if (endRaw.compareTo(BigInteger.ZERO) >= 0) {
            long start = 0;
            long end = endRaw.longValue();
            if (end > k - 1)
                end = k - 1;

            if (start <= end) {
                long length = end - start + 1;
                long excStart = Math.max(start, end - 61);
                long excCount = (excStart <= end) ? (end - excStart + 1) : 0;
                long bulk = length - excCount;

                long constant = ctx.prefixK[r + 1];
                addBulk.accept(bulk, constant);

                for (long n = excStart; n <= end; ++n) {
                    tasks.add(new Task(n, s));
                }
            }
        }

        for (Task task : tasks) {
            total[0] = modAdd(total[0], exceptionContrib(ctx, task.n, task.s));
        }

        return total[0] % MOD;
    }

    public static String solve() {
        long k = 1000000000000000000L + 31L;
        long t = 100000000000000L + 31L;
        int r = 62;
        return Long.toString(computeFast(k, t, r));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}