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

public class Euler324 {
    static final int MOD = 100000007;
    static final int CELLS = 9;
    static final int FULL_MASK = (1 << CELLS) - 1;
    static final int STATE_COUNT = 1 << CELLS;

    static int addMod(int a, int b) {
        int x = a + b;
        return x >= MOD ? x - MOD : x;
    }

    static int subMod(int a, int b) {
        int x = a - b;
        return x < 0 ? x + MOD : x;
    }

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

    static int powMod(int base, long exp) {
        int res = 1;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = mulMod(res, base);
            base = mulMod(base, base);
            exp >>= 1;
        }
        return res;
    }

    static int invMod(int a) {
        return powMod(a, MOD - 2);
    }

    static void dfsLayerFill(int filledMask, int nextMask, int[] ways) {
        if (filledMask == FULL_MASK) {
            ways[nextMask]++;
            return;
        }

        int freeBits = (~filledMask) & FULL_MASK;
        int bit = Integer.numberOfTrailingZeros(freeBits);

        dfsLayerFill(filledMask | (1 << bit), nextMask | (1 << bit), ways);

        int r = bit / 3;
        int c = bit % 3;

        if (c < 2 && (filledMask & (1 << (bit + 1))) == 0) {
            dfsLayerFill(filledMask | (1 << bit) | (1 << (bit + 1)), nextMask, ways);
        }

        if (r < 2 && (filledMask & (1 << (bit + 3))) == 0) {
            dfsLayerFill(filledMask | (1 << bit) | (1 << (bit + 3)), nextMask, ways);
        }
    }

    static class Edge {
        int nxt, cnt;

        Edge(int nxt, int cnt) {
            this.nxt = nxt;
            this.cnt = cnt;
        }
    }

    @SuppressWarnings("unchecked")
    static List<Edge>[] buildTransitions() {
        List<Edge>[] transitions = new List[STATE_COUNT];
        for (int mask = 0; mask < STATE_COUNT; ++mask) {
            int[] ways = new int[STATE_COUNT];
            dfsLayerFill(mask, 0, ways);
            transitions[mask] = new ArrayList<>();
            for (int nxt = 0; nxt < STATE_COUNT; ++nxt) {
                if (ways[nxt] > 0) {
                    transitions[mask].add(new Edge(nxt, ways[nxt] % MOD));
                }
            }
        }
        return transitions;
    }

    static int[] generateSequence(int terms, List<Edge>[] transitions) {
        int[] seq = new int[terms + 1];
        int[] current = new int[STATE_COUNT];
        int[] next = new int[STATE_COUNT];

        current[0] = 1;
        seq[0] = 1;

        for (int step = 1; step <= terms; ++step) {
            Arrays.fill(next, 0);
            for (int mask = 0; mask < STATE_COUNT; ++mask) {
                int value = current[mask];
                if (value == 0)
                    continue;
                for (Edge e : transitions[mask]) {
                    next[e.nxt] = addMod(next[e.nxt], mulMod(value, e.cnt));
                }
            }
            System.arraycopy(next, 0, current, 0, STATE_COUNT);
            seq[step] = current[0];
        }
        return seq;
    }

    static int[] berlekampMassey(int[] sequence) {
        List<Integer> C = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        C.add(1);
        B.add(1);

        int L = 0, m = 1, b = 1;

        for (int n = 0; n < sequence.length; ++n) {
            int d = sequence[n];
            for (int i = 1; i <= L; ++i) {
                if (i < C.size()) {
                    d = addMod(d, mulMod(C.get(i), sequence[n - i]));
                }
            }

            if (d == 0) {
                m++;
                continue;
            }

            List<Integer> T = new ArrayList<>(C);
            int coef = mulMod(d, invMod(b));

            while (C.size() < B.size() + m) {
                C.add(0);
            }

            for (int i = 0; i < B.size(); ++i) {
                C.set(i + m, subMod(C.get(i + m), mulMod(coef, B.get(i))));
            }

            if (2 * L <= n) {
                L = n + 1 - L;
                B = T;
                b = d;
                m = 1;
            } else {
                m++;
            }
        }

        int[] recurrence = new int[L];
        for (int i = 1; i <= L; ++i) {
            recurrence[i - 1] = (MOD - C.get(i)) % MOD;
        }
        return recurrence;
    }

    static int[] combinePolynomials(int[] a, int[] b, int[] recurrence) {
        int k = recurrence.length;
        int[] prod = new int[2 * k];

        for (int i = 0; i < k; ++i) {
            if (a[i] == 0)
                continue;
            for (int j = 0; j < k; ++j) {
                if (b[j] == 0)
                    continue;
                prod[i + j] = addMod(prod[i + j], mulMod(a[i], b[j]));
            }
        }

        for (int i = 2 * k - 2; i >= k; --i) {
            int coef = prod[i];
            if (coef == 0)
                continue;
            for (int j = 1; j <= k; ++j) {
                prod[i - j] = addMod(prod[i - j], mulMod(coef, recurrence[j - 1]));
            }
        }

        int[] res = new int[k];
        System.arraycopy(prod, 0, res, 0, k);
        return res;
    }

    static int linearRecurrenceNth(int[] initial, int[] recurrence, List<Integer> bitsLsbFirst) {
        int k = recurrence.length;
        int[] result = new int[k];
        result[0] = 1;

        int[] xPoly = new int[k];
        if (k == 1)
            xPoly[0] = recurrence[0];
        else
            xPoly[1] = 1;

        for (int bit : bitsLsbFirst) {
            if (bit != 0) {
                result = combinePolynomials(result, xPoly, recurrence);
            }
            xPoly = combinePolynomials(xPoly, xPoly, recurrence);
        }

        int answer = 0;
        for (int i = 0; i < k; ++i) {
            answer = addMod(answer, mulMod(result[i], initial[i]));
        }
        return answer;
    }

    static List<Integer> bitsFromDecimal(String valueStr) {
        BigInteger val = new BigInteger(valueStr);
        List<Integer> bits = new ArrayList<>();
        if (val.equals(BigInteger.ZERO)) {
            bits.add(0);
            return bits;
        }
        while (val.compareTo(BigInteger.ZERO) > 0) {
            bits.add(val.testBit(0) ? 1 : 0);
            val = val.shiftRight(1);
        }
        return bits;
    }

    public static String solve() {
        List<Edge>[] transitions = buildTransitions();
        int[] seq = generateSequence(1300, transitions);
        int[] recurrence = berlekampMassey(seq);

        int[] initial = new int[recurrence.length];
        System.arraycopy(seq, 0, initial, 0, recurrence.length);

        StringBuilder sb = new StringBuilder();
        sb.append("1");
        for (int i = 0; i < 10000; i++)
            sb.append("0");
        String exponentStr = sb.toString();

        List<Integer> bits = bitsFromDecimal(exponentStr);
        int ans = linearRecurrenceNth(initial, recurrence, bits);
        return String.valueOf(ans);
    }

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