import java.util.*;
import java.math.BigInteger;

public class Euler923 {

    static final int MOD = 1000000007;

    static class Dyadic {
        long num;
        int exp;

        Dyadic(long num, int exp) {
            this.num = num;
            this.exp = exp;
            normalize();
        }

        void normalize() {
            if (num == 0) {
                exp = 0;
                return;
            }
            while (exp > 0 && (num & 1) == 0) {
                num >>= 1;
                exp--;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof Dyadic))
                return false;
            Dyadic dyadic = (Dyadic) o;
            return num == dyadic.num && exp == dyadic.exp;
        }

        @Override
        public int hashCode() {
            return Objects.hash(num, exp);
        }
    }

    static int cmpDyadic(Dyadic a, Dyadic b) {
        if (a.num == b.num && a.exp == b.exp)
            return 0;
        int e = Math.max(a.exp, b.exp);
        BigInteger na = BigInteger.valueOf(a.num).shiftLeft(e - a.exp);
        BigInteger nb = BigInteger.valueOf(b.num).shiftLeft(e - b.exp);
        return na.compareTo(nb);
    }

    static Dyadic addDyadic(Dyadic a, Dyadic b) {
        int e = Math.max(a.exp, b.exp);
        BigInteger na = BigInteger.valueOf(a.num).shiftLeft(e - a.exp);
        BigInteger nb = BigInteger.valueOf(b.num).shiftLeft(e - b.exp);
        BigInteger sum = na.add(nb);
        return new Dyadic(sum.longValue(), e);
    }

    static Dyadic negDyadic(Dyadic a) {
        return new Dyadic(-a.num, a.exp);
    }

    static long floorDyadic(Dyadic a) {
        if (a.exp == 0)
            return a.num;
        long den = 1L << a.exp;
        if (a.num >= 0)
            return a.num / den;
        return -(((-a.num) + den - 1) / den);
    }

    static long ceilDyadic(Dyadic a) {
        return -floorDyadic(negDyadic(a));
    }

    static Dyadic simplestBetween(Dyadic l, Dyadic r) {
        for (int n = 0; n <= 60; ++n) {
            int finalN = n;
            java.util.function.Function<Dyadic, Long> floorScaled = (x) -> {
                if (finalN >= x.exp) {
                    return x.num << (finalN - x.exp);
                }
                int sh = x.exp - finalN;
                if (x.num >= 0)
                    return x.num >> sh;
                long pos = -x.num;
                long q = (pos + (1L << sh) - 1) >> sh;
                return -q;
            };
            java.util.function.Function<Dyadic, Long> ceilScaled = (x) -> {
                return -floorScaled.apply(negDyadic(x));
            };

            long low = floorScaled.apply(l) + 1;
            long high = ceilScaled.apply(r) - 1;
            if (low > high)
                continue;

            long t;
            if (low <= 0 && 0 <= high)
                t = 0;
            else if (high < 0)
                t = high;
            else
                t = low;
            return new Dyadic(t, finalN);
        }
        return new Dyadic(0, 0);
    }

    static class GameNode {
        boolean isNumber = false;
        boolean reduced = false;
        Dyadic val = null;
        List<Integer> L = new ArrayList<>();
        List<Integer> R = new ArrayList<>();
    }

    static class StopPair {
        Dyadic L, R;

        StopPair(Dyadic l, Dyadic r) {
            L = l;
            R = r;
        }
    }

    static class GameEngine {
        List<GameNode> nodes = new ArrayList<>();
        List<Integer> parent = new ArrayList<>();

        Map<Dyadic, Integer> numMap = new HashMap<>();
        Map<String, Integer> binMap = new HashMap<>();
        Map<String, Integer> canonMap = new HashMap<>();
        Map<String, Boolean> leqMemo = new HashMap<>();

        List<StopPair> stopMemo = new ArrayList<>();
        List<Boolean> stopSeen = new ArrayList<>();
        int zeroId;

        GameEngine() {
            zeroId = makeNumber(new Dyadic(0, 0));
        }

        int zero() {
            return zeroId;
        }

        int rep(int x) {
            while (parent.get(x) != x) {
                int px = parent.get(x);
                parent.set(x, parent.get(px));
                x = parent.get(x);
            }
            return x;
        }

        int canonical(int id) {
            return rep(id);
        }

        int makeNumber(Dyadic inStr) {
            Dyadic val = new Dyadic(inStr.num, inStr.exp);
            if (numMap.containsKey(val))
                return numMap.get(val);

            int id = nodes.size();
            GameNode node = new GameNode();
            node.isNumber = true;
            node.reduced = true;
            node.val = val;
            nodes.add(node);
            parent.add(id);
            numMap.put(val, id);

            if (val.num == 0)
                return id;

            if (val.exp == 0) {
                if (val.num > 0) {
                    node.L.add(makeNumber(new Dyadic(val.num - 1, 0)));
                } else {
                    node.R.add(makeNumber(new Dyadic(val.num + 1, 0)));
                }
            } else {
                node.L.add(makeNumber(new Dyadic(val.num - 1, val.exp)));
                node.R.add(makeNumber(new Dyadic(val.num + 1, val.exp)));
            }
            return id;
        }

        int makeBinary(int l, int r) {
            if (l != -1)
                l = rep(l);
            if (r != -1)
                r = rep(r);
            String key = l + "," + r;
            if (binMap.containsKey(key))
                return rep(binMap.get(key));

            int id = nodes.size();
            GameNode node = new GameNode();
            nodes.add(node);
            parent.add(id);
            if (l != -1)
                node.L.add(l);
            if (r != -1)
                node.R.add(r);

            int rid = reduceInPlace(id);
            binMap.put(key, rid);
            return rid;
        }

        void aliasTo(int fromId, int toId) {
            fromId = rep(fromId);
            toId = rep(toId);
            if (fromId != toId) {
                parent.set(fromId, toId);
            }
        }

        boolean leq(int a, int b) {
            a = rep(a);
            b = rep(b);
            if (a == b)
                return true;
            GameNode na = nodes.get(a);
            GameNode nb = nodes.get(b);
            if (na.isNumber && nb.isNumber) {
                return cmpDyadic(na.val, nb.val) <= 0;
            }

            String key = a + "," + b;
            if (leqMemo.containsKey(key))
                return leqMemo.get(key);

            for (int al : na.L) {
                if (leq(b, al)) {
                    leqMemo.put(key, false);
                    return false;
                }
            }
            for (int br : nb.R) {
                if (leq(br, a)) {
                    leqMemo.put(key, false);
                    return false;
                }
            }
            leqMemo.put(key, true);
            return true;
        }

        List<Integer> removeDominatedLeft(List<Integer> L) {
            boolean[] kill = new boolean[L.size()];
            for (int i = 0; i < L.size(); ++i) {
                if (kill[i])
                    continue;
                for (int j = 0; j < L.size(); ++j) {
                    if (i == j || kill[j])
                        continue;
                    if (leq(L.get(i), L.get(j)) && !leq(L.get(j), L.get(i))) {
                        kill[i] = true;
                        break;
                    }
                }
            }
            List<Integer> out = new ArrayList<>();
            for (int i = 0; i < L.size(); ++i) {
                if (!kill[i])
                    out.add(L.get(i));
            }
            return out;
        }

        List<Integer> removeDominatedRight(List<Integer> R) {
            boolean[] kill = new boolean[R.size()];
            for (int i = 0; i < R.size(); ++i) {
                if (kill[i])
                    continue;
                for (int j = 0; j < R.size(); ++j) {
                    if (i == j || kill[j])
                        continue;
                    if (leq(R.get(j), R.get(i)) && !leq(R.get(i), R.get(j))) {
                        kill[i] = true;
                        break;
                    }
                }
            }
            List<Integer> out = new ArrayList<>();
            for (int i = 0; i < R.size(); ++i) {
                if (!kill[i])
                    out.add(R.get(i));
            }
            return out;
        }

        List<Integer> distinctAndSorted(List<Integer> lst) {
            Set<Integer> set = new HashSet<>(lst);
            List<Integer> out = new ArrayList<>(set);
            Collections.sort(out);
            return out;
        }

        int reduceInPlace(int id) {
            id = rep(id);
            GameNode node = nodes.get(id);
            if (node.isNumber || node.reduced)
                return id;

            List<Integer> L = new ArrayList<>();
            for (int x : node.L)
                L.add(rep(x));
            List<Integer> R = new ArrayList<>();
            for (int x : node.R)
                R.add(rep(x));

            L = distinctAndSorted(L);
            R = distinctAndSorted(R);

            L = removeDominatedLeft(L);
            R = removeDominatedRight(R);

            boolean changed = true;
            while (changed) {
                changed = false;
                for (int i = 0; i < L.size(); ++i) {
                    int l = rep(L.get(i));
                    boolean found = false;
                    for (int lr : nodes.get(l).R) {
                        if (leq(lr, id)) {
                            L.remove(i);
                            int lrRep = rep(lr);
                            for (int x : nodes.get(lrRep).L) {
                                L.add(rep(x));
                            }
                            changed = true;
                            found = true;
                            break;
                        }
                    }
                    if (found)
                        break;
                }
                if (changed) {
                    L = distinctAndSorted(L);
                    L = removeDominatedLeft(L);
                    continue;
                }

                for (int i = 0; i < R.size(); ++i) {
                    int r = rep(R.get(i));
                    boolean found = false;
                    for (int rl : nodes.get(r).L) {
                        if (leq(id, rl)) {
                            R.remove(i);
                            int rlRep = rep(rl);
                            for (int x : nodes.get(rlRep).R) {
                                R.add(rep(x));
                            }
                            changed = true;
                            found = true;
                            break;
                        }
                    }
                    if (found)
                        break;
                }
                if (changed) {
                    R = distinctAndSorted(R);
                    R = removeDominatedRight(R);
                }
            }

            if (L.isEmpty() && R.isEmpty()) {
                aliasTo(id, zeroId);
                return zeroId;
            }

            boolean lNum = true;
            for (int x : L)
                if (!nodes.get(rep(x)).isNumber) {
                    lNum = false;
                    break;
                }
            boolean rNum = true;
            for (int x : R)
                if (!nodes.get(rep(x)).isNumber) {
                    rNum = false;
                    break;
                }

            if (!L.isEmpty() && !R.isEmpty() && lNum && rNum) {
                Dyadic maxL = nodes.get(rep(L.get(0))).val;
                for (int x : L) {
                    Dyadic v = nodes.get(rep(x)).val;
                    if (cmpDyadic(v, maxL) > 0)
                        maxL = v;
                }
                Dyadic minR = nodes.get(rep(R.get(0))).val;
                for (int x : R) {
                    Dyadic v = nodes.get(rep(x)).val;
                    if (cmpDyadic(v, minR) < 0)
                        minR = v;
                }
                if (cmpDyadic(maxL, minR) < 0) {
                    Dyadic mid = simplestBetween(maxL, minR);
                    int nid = makeNumber(mid);
                    aliasTo(id, nid);
                    return nid;
                }
            } else if (lNum && R.isEmpty()) {
                Dyadic maxL = nodes.get(rep(L.get(0))).val;
                for (int x : L) {
                    Dyadic v = nodes.get(rep(x)).val;
                    if (cmpDyadic(v, maxL) > 0)
                        maxL = v;
                }
                long fl = floorDyadic(maxL);
                int nid = makeNumber(new Dyadic(fl + 1, 0));
                aliasTo(id, nid);
                return nid;
            } else if (rNum && L.isEmpty()) {
                Dyadic minR = nodes.get(rep(R.get(0))).val;
                for (int x : R) {
                    Dyadic v = nodes.get(rep(x)).val;
                    if (cmpDyadic(v, minR) < 0)
                        minR = v;
                }
                long ce = ceilDyadic(minR);
                int nid = makeNumber(new Dyadic(ce - 1, 0));
                aliasTo(id, nid);
                return nid;
            }

            String key = L.toString() + "|" + R.toString();
            if (canonMap.containsKey(key)) {
                int cId = canonMap.get(key);
                aliasTo(id, cId);
                return rep(cId);
            }

            canonMap.put(key, id);
            node.L = L;
            node.R = R;
            node.reduced = true;
            return id;
        }

        void ensureStopSize(int id) {
            while (stopMemo.size() <= id) {
                stopMemo.add(null);
                stopSeen.add(false);
            }
        }

        StopPair stops(int id) {
            id = rep(id);
            ensureStopSize(id);
            if (stopSeen.get(id))
                return stopMemo.get(id);

            GameNode node = nodes.get(id);
            StopPair res;
            if (node.isNumber) {
                res = new StopPair(node.val, node.val);
            } else {
                boolean hasL = false;
                boolean hasR = false;
                Dyadic Lval = null;
                Dyadic Rval = null;
                for (int l : node.L) {
                    StopPair sp = stops(l);
                    if (!hasL || cmpDyadic(sp.R, Lval) > 0) {
                        Lval = sp.R;
                        hasL = true;
                    }
                }
                for (int r : node.R) {
                    StopPair sp = stops(r);
                    if (!hasR || cmpDyadic(sp.L, Rval) < 0) {
                        Rval = sp.L;
                        hasR = true;
                    }
                }
                res = new StopPair(Lval, Rval);
            }

            stopMemo.set(id, res);
            stopSeen.set(id, true);
            return res;
        }
    }

    static class StaircaseFreq {
        Map<Integer, Integer> numFreq = new HashMap<>();
        List<Map<Integer, Integer>> switchFreq = new ArrayList<>();
        int maxWeight = 0;
    }

    static StaircaseFreq collectStaircaseFreq(int maxW, GameEngine eng) {
        StaircaseFreq freq = new StaircaseFreq();
        for (int i = 0; i <= maxW; ++i) {
            freq.switchFreq.add(new HashMap<>());
        }

        for (int a = 1; a <= maxW - 1; ++a) {
            for (int b = 1; b <= maxW - a; ++b) {
                int K = maxW - a - b;
                if (K < 1)
                    continue;

                int A = a;
                int B = b;
                int[] dp = new int[(K + 1) * A * B];
                Arrays.fill(dp, eng.zero());

                for (int k = 1; k <= K; ++k) {
                    for (int i = A - 1; i >= 0; --i) {
                        for (int j = B - 1; j >= 0; --j) {
                            int left = -1;
                            int right = -1;

                            if (k == 1 && j == B - 1)
                                left = -1;
                            else if (j < B - 1)
                                left = dp[(k * A + i) * B + (j + 1)];
                            else
                                left = dp[((k - 1) * A + i) * B + 0];

                            if (k == 1 && i == A - 1)
                                right = -1;
                            else if (i < A - 1)
                                right = dp[(k * A + (i + 1)) * B + j];
                            else
                                right = dp[((k - 1) * A + 0) * B + j];

                            dp[(k * A + i) * B + j] = eng.makeBinary(left, right);
                        }
                    }
                }

                for (int k = 1; k <= K; ++k) {
                    int id = eng.canonical(dp[(k * A + 0) * B + 0]);
                    StopPair sp = eng.stops(id);
                    int L = (int) sp.L.num;
                    int R = (int) sp.R.num;
                    GameNode node = eng.nodes.get(id);
                    if (node.isNumber) {
                        freq.numFreq.put(L, (freq.numFreq.getOrDefault(L, 0) + 1) % MOD);
                    } else {
                        int weight = L - R;
                        while (weight >= freq.switchFreq.size()) {
                            freq.switchFreq.add(new HashMap<>());
                        }
                        Map<Integer, Integer> map = freq.switchFreq.get(weight);
                        map.put(R, (map.getOrDefault(R, 0) + 1) % MOD);
                        freq.maxWeight = Math.max(freq.maxWeight, weight);
                    }
                }
            }
        }
        return freq;
    }

    static List<Map<Integer, Integer>> computeDist(Map<Integer, Integer> baseFreq, int maxLen) {
        List<Map<Integer, Integer>> dist = new ArrayList<>();
        for (int i = 0; i <= maxLen; ++i)
            dist.add(new HashMap<>());
        dist.get(0).put(0, 1);

        if (baseFreq.isEmpty())
            return dist;

        for (int length = 1; length <= maxLen; ++length) {
            Map<Integer, Integer> cur = dist.get(length);
            Map<Integer, Integer> prev = dist.get(length - 1);
            for (Map.Entry<Integer, Integer> pv : prev.entrySet()) {
                int vsum = pv.getKey();
                int cnt = pv.getValue();
                for (Map.Entry<Integer, Integer> bv : baseFreq.entrySet()) {
                    int val = bv.getKey();
                    int freq = bv.getValue();
                    long ways = (long) cnt * freq % MOD;
                    cur.put(vsum + val, (int) ((cur.getOrDefault(vsum + val, 0) + ways) % MOD));
                }
            }
        }
        return dist;
    }

    static class StateKey {
        int sumR, sumOdd;

        StateKey(int r, int o) {
            sumR = r;
            sumOdd = o;
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof StateKey))
                return false;
            StateKey stateKey = (StateKey) o;
            return sumR == stateKey.sumR && sumOdd == stateKey.sumOdd;
        }

        public int hashCode() {
            return Objects.hash(sumR, sumOdd);
        }
    }

    static int computeS(int m, int maxW, GameEngine eng) {
        StaircaseFreq freq = collectStaircaseFreq(maxW, eng);

        int[][] binom = new int[m + 1][m + 1];
        for (int n = 0; n <= m; ++n) {
            binom[n][0] = binom[n][n] = 1;
            for (int k = 1; k < n; ++k) {
                binom[n][k] = (binom[n - 1][k - 1] + binom[n - 1][k]) % MOD;
            }
        }

        List<Map<Integer, Integer>> numDist = computeDist(freq.numFreq, m);
        List<List<Map<Integer, Integer>>> distByWeight = new ArrayList<>();
        for (int w = 0; w <= freq.maxWeight; ++w) {
            if (freq.switchFreq.get(w).isEmpty()) {
                distByWeight.add(new ArrayList<>());
            } else {
                distByWeight.add(computeDist(freq.switchFreq.get(w), m));
            }
        }

        Map<StateKey, Integer>[][] dp = new Map[m + 1][2];
        for (int s = 0; s <= m; ++s) {
            for (int p = 0; p < 2; ++p)
                dp[s][p] = new HashMap<>();
        }
        dp[0][0].put(new StateKey(0, 0), 1);

        for (int w = freq.maxWeight; w >= 0; --w) {
            List<Map<Integer, Integer>> distW = distByWeight.get(w);
            if (distW.isEmpty())
                continue;

            Map<StateKey, Integer>[][] nextDp = new Map[m + 1][2];
            for (int s = 0; s <= m; ++s) {
                for (int p = 0; p < 2; ++p)
                    nextDp[s][p] = new HashMap<>();
            }

            for (int s = 0; s <= m; ++s) {
                for (int parity = 0; parity < 2; ++parity) {
                    Map<StateKey, Integer> cur = dp[s][parity];
                    if (cur.isEmpty())
                        continue;

                    for (Map.Entry<StateKey, Integer> kv : cur.entrySet()) {
                        int sumR = kv.getKey().sumR;
                        int sumOdd = kv.getKey().sumOdd;
                        int cnt = kv.getValue();

                        for (int c = 0; c <= m - s; ++c) {
                            Map<Integer, Integer> distC = distW.get(c);
                            if (distC == null || distC.isEmpty())
                                continue;

                            int leftCount = (c + (parity == 0 ? 1 : 0)) / 2;
                            int newParity = parity ^ (c & 1);
                            int comb = binom[s + c][c];

                            for (Map.Entry<Integer, Integer> rv : distC.entrySet()) {
                                int newS = s + c;
                                int newSumR = sumR + rv.getKey();
                                int newSumOdd = sumOdd + leftCount * w;
                                long ways = (long) cnt * rv.getValue() % MOD;
                                ways = ways * comb % MOD;

                                StateKey key = new StateKey(newSumR, newSumOdd);
                                nextDp[newS][newParity].put(key,
                                        (int) ((nextDp[newS][newParity].getOrDefault(key, 0) + ways) % MOD));
                            }
                        }
                    }
                }
            }
            dp = nextDp;
        }

        long ans = 0;
        for (int s = 0; s <= m; ++s) {
            int n = m - s;
            int interleave = binom[m][s];
            for (int parity = 0; parity < 2; ++parity) {
                Map<StateKey, Integer> cur = dp[s][parity];
                if (cur.isEmpty())
                    continue;

                for (Map.Entry<StateKey, Integer> kv : cur.entrySet()) {
                    int sumR = kv.getKey().sumR;
                    int sumOdd = kv.getKey().sumOdd;
                    int cnt = kv.getValue();
                    Map<Integer, Integer> numMap = numDist.get(n);

                    for (Map.Entry<Integer, Integer> nv : numMap.entrySet()) {
                        long totalVal = (long) sumR + sumOdd + nv.getKey();
                        boolean win;
                        if (totalVal > 0)
                            win = true;
                        else if (totalVal < 0)
                            win = false;
                        else
                            win = (s % 2 == 1);

                        if (!win)
                            continue;

                        long ways = (long) cnt * nv.getValue() % MOD;
                        ways = ways * interleave % MOD;
                        ans = (ans + ways) % MOD;
                    }
                }
            }
        }

        return (int) (ans % MOD);
    }

    public static String solve() {
        GameEngine eng = new GameEngine();
        int ans = computeS(8, 64, eng);
        return Integer.toString(ans);
    }

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