import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class Euler968 {

    static final int MOD = 1000000007;
    static final int VARS = 5;
    static final int EDGES = 10;
    static final int BITS = 31;
    static final int[] POW3 = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 };
    static final int STATE_COUNT = 59049;
    static final int[][] EDGE_ENDPOINTS = {
            { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 4 }, { 1, 2 },
            { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 }
    };
    static final int[] BASES = { 2, 3, 5, 7, 11 };

    static byte[][] CARRY_DIGITS = new byte[STATE_COUNT][EDGES];
    static byte[][] PAIR_BITS = new byte[32][EDGES];
    static int[][] BIT_FACTORS = new int[BITS][32];

    static void buildTables() {
        for (int s = 0; s < STATE_COUNT; ++s) {
            int t = s;
            for (int e = 0; e < EDGES; ++e) {
                CARRY_DIGITS[s][e] = (byte) (t % 3);
                t /= 3;
            }
        }

        for (int mask = 0; mask < 32; ++mask) {
            for (int e = 0; e < EDGES; ++e) {
                int u = EDGE_ENDPOINTS[e][0];
                int v = EDGE_ENDPOINTS[e][1];
                int bitU = (mask >> u) & 1;
                int bitV = (mask >> v) & 1;
                PAIR_BITS[mask][e] = (byte) (bitU + bitV);
            }
        }

        int[][] powers = new int[VARS][BITS];
        for (int i = 0; i < VARS; ++i) {
            powers[i][0] = BASES[i] % MOD;
            for (int k = 1; k < BITS; ++k) {
                long v = powers[i][k - 1];
                powers[i][k] = (int) ((v * v) % MOD);
            }
        }

        for (int k = 0; k < BITS; ++k) {
            for (int mask = 0; mask < 32; ++mask) {
                long value = 1;
                for (int i = 0; i < VARS; ++i) {
                    if (((mask >> i) & 1) == 1) {
                        value = (value * powers[i][k]) % MOD;
                    }
                }
                BIT_FACTORS[k][mask] = (int) value;
            }
        }
    }

    static int computeP(int[] bounds) {
        byte[][] boundBits = new byte[BITS][EDGES];
        for (int k = 0; k < BITS; ++k) {
            for (int e = 0; e < EDGES; ++e) {
                boundBits[k][e] = (byte) ((bounds[e] >> k) & 1);
            }
        }

        int[] cur = new int[STATE_COUNT];
        int[] nxt = new int[STATE_COUNT];
        int[] active = new int[STATE_COUNT];
        int[] nextActive = new int[STATE_COUNT];
        int activeCount = 1;
        int nextActiveCount = 0;

        active[0] = 0;
        cur[0] = 1;

        for (int k = 0; k < BITS; ++k) {
            nextActiveCount = 0;
            byte[] bits = boundBits[k];
            int[] bitFactorsK = BIT_FACTORS[k];

            for (int aidx = 0; aidx < activeCount; ++aidx) {
                int state = active[aidx];
                int stateValue = cur[state];
                if (stateValue == 0)
                    continue;
                cur[state] = 0;

                byte[] carry = CARRY_DIGITS[state];

                for (int mask = 0; mask < 32; ++mask) {
                    byte[] pair = PAIR_BITS[mask];
                    int nextState = 0;
                    for (int e = 0; e < EDGES; ++e) {
                        int t = pair[e] + carry[e] - bits[e];
                        int nextCarry = (t <= 0) ? 0 : ((t + 1) >> 1);
                        if (nextCarry != 0) {
                            nextState += nextCarry * POW3[e];
                        }
                    }

                    long add = ((long) stateValue * bitFactorsK[mask]) % MOD;
                    int dst = nxt[nextState];
                    if (dst == 0) {
                        nextActive[nextActiveCount++] = nextState;
                    }
                    dst += add;
                    if (dst >= MOD)
                        dst -= MOD;
                    nxt[nextState] = dst;
                }
            }

            int[] tempActive = active;
            active = nextActive;
            nextActive = tempActive;
            activeCount = nextActiveCount;

            int[] tempCur = cur;
            cur = nxt;
            nxt = tempCur;
        }

        return cur[0];
    }

    public static String solve() {
        buildTables();

        int[] a = new int[1000];
        a[0] = 1;
        a[1] = 7;
        for (int i = 2; i < 1000; ++i) {
            long term = (7L * a[i - 1] + (long) a[i - 2] * a[i - 2]) % MOD;
            a[i] = (int) term;
        }

        int total = IntStream.range(0, 100).parallel().map(n -> {
            int[] bounds = new int[EDGES];
            for (int e = 0; e < EDGES; ++e) {
                bounds[e] = a[10 * n + e];
            }
            return computeP(bounds);
        }).reduce(0, (acc, val) -> {
            int sum = acc + val;
            return sum >= MOD ? sum - MOD : sum;
        });

        return Integer.toString(total);
    }

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