import java.util.*;

public class Euler949 {
    static final long MOD = 1001001011;

    public static String solve() {
        int n = 20, k = 7;
        int e = n;
        int total = (1 << (n + 1)) - 1;
        long scale = 1L << e;
        long[] dpU = new long[total], dpD = new long[total];
        dpU[1] = scale;
        dpD[1] = scale;
        dpU[2] = -scale;
        dpD[2] = -scale;
        int[] hot = new int[1 << n];
        long INF = Long.MAX_VALUE / 2;
        for (int length = 2; length <= n; length++) {
            int size = 1 << length;
            int start = size - 1;
            boolean isFinal = (length == n);
            for (int bits = 0; bits < size; bits++) {
                long uRaw = -INF;
                for (int sLen = 1; sLen < length; sLen++) {
                    int suf = bits & ((1 << sLen) - 1);
                    int idx = (1 << sLen) - 1 + suf;
                    if (dpD[idx] > uRaw)
                        uRaw = dpD[idx];
                }
                long dRaw = INF;
                for (int pLen = 1; pLen < length; pLen++) {
                    int pre = bits >> (length - pLen);
                    int idx = (1 << pLen) - 1 + pre;
                    if (dpU[idx] < dRaw)
                        dRaw = dpU[idx];
                }
                int idx2 = start + bits;
                if (uRaw < dRaw) {
                    long x = simplestBetween(uRaw, dRaw, e);
                    dpU[idx2] = x;
                    dpD[idx2] = x;
                    if (isFinal)
                        hot[bits] = 0;
                } else {
                    dpU[idx2] = uRaw;
                    dpD[idx2] = dRaw;
                    if (isFinal)
                        hot[bits] = 1;
                }
            }
        }
        int startN = (1 << n) - 1;
        long[] uFull = new long[1 << n];
        System.arraycopy(dpU, startN, uFull, 0, 1 << n);

        Map<Long, Long> histAll = new HashMap<>(), histCold = new HashMap<>();
        for (int i = 0; i < uFull.length; i++) {
            histAll.merge(uFull[i], 1L, (a, b) -> (a + b) % MOD);
            if (hot[i] == 0)
                histCold.merge(uFull[i], 1L, (a, b) -> (a + b) % MOD);
        }
        int a2 = k / 2, b2 = k - a2;
        Map<Long, Long> distA = powSmall(histAll, a2), distB = powSmall(histAll, b2);
        long neg = countSumLt0(distA, distB);
        Map<Long, Long> coldA = powSmall(histCold, a2), coldB = powSmall(histCold, b2);
        long zeroCold = countSumEq0(coldA, coldB);
        return String.valueOf((neg + zeroCold) % MOD);
    }

    static long simplestBetween(long u, long d, int e) {
        for (int m = 0; m <= e; m++) {
            int s = e - m;
            long pMin = fdp2(u, s) + 1, pMax = cdp2(d, s) - 1;
            if (pMin > pMax)
                continue;
            long p = pMin > 0 ? pMin : (pMax < 0 ? pMax : 0);
            if (m > 0 && p != 0 && p % 2 == 0) {
                if (p + 1 <= pMax && (p + 1) % 2 != 0)
                    p++;
                else if (p - 1 >= pMin && (p - 1) % 2 != 0)
                    p--;
            }
            return p << s;
        }
        return 0;
    }

    static long fdp2(long x, int s) {
        if (s == 0)
            return x;
        if (x >= 0)
            return x >> s;
        return -((-x + (1L << s) - 1) >> s);
    }

    static long cdp2(long x, int s) {
        if (s == 0)
            return x;
        if (x >= 0)
            return (x + (1L << s) - 1) >> s;
        return -((-x) >> s);
    }

    static Map<Long, Long> conv(Map<Long, Long> a, Map<Long, Long> b) {
        Map<Long, Long> out = new HashMap<>();
        for (var ea : a.entrySet())
            for (var eb : b.entrySet())
                out.merge(ea.getKey() + eb.getKey(), ea.getValue() * eb.getValue() % MOD, (x, y) -> (x + y) % MOD);
        return out;
    }

    static Map<Long, Long> powSmall(Map<Long, Long> hist, int t) {
        if (t == 0)
            return Map.of(0L, 1L);
        Map<Long, Long> d = new HashMap<>(hist);
        for (int i = 1; i < t; i++)
            d = conv(d, hist);
        return d;
    }

    static long countSumLt0(Map<Long, Long> a, Map<Long, Long> b) {
        List<Map.Entry<Long, Long>> items = new ArrayList<>(b.entrySet());
        items.sort(Comparator.comparingLong(Map.Entry::getKey));
        long[] keys = new long[items.size()];
        long[] pref = new long[items.size() + 1];
        for (int i = 0; i < items.size(); i++) {
            keys[i] = items.get(i).getKey();
            pref[i + 1] = (pref[i] + items.get(i).getValue()) % MOD;
        }
        long ans = 0;
        for (var ea : a.entrySet()) {
            long target = -ea.getKey();
            int idx = lowerBound(keys, target);
            ans = (ans + ea.getValue() * pref[idx]) % MOD;
        }
        return ans;
    }

    static long countSumEq0(Map<Long, Long> a, Map<Long, Long> b) {
        long ans = 0;
        for (var ea : a.entrySet()) {
            Long v = b.get(-ea.getKey());
            if (v != null)
                ans = (ans + ea.getValue() * v) % MOD;
        }
        return ans;
    }

    static int lowerBound(long[] arr, long target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }

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