import java.util.*;

public class Euler696 {
    static final long MOD = 1000000007L;

    static long modPow(long a, long e) {
        long r = 1;
        a %= MOD;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (r * a) % MOD;
            a = (a * a) % MOD;
            e >>= 1;
        }
        return r;
    }

    static class Block {
        int len, tiles, count;

        Block(int l, int t, int c) {
            len = l;
            tiles = t;
            count = c;
        }
    }

    static class DFA {
        int[][] trans;
        int[] accept0;
        int[] accept1;
    }

    static DFA buildDFA() {
        int nfaStates = 50;
        long[][] nfa = new long[nfaStates][5];

        for (int p = 0; p <= 1; ++p) {
            for (int a = 0; a <= 4; ++a) {
                for (int b = 0; b <= 4; ++b) {
                    int sid = p * 25 + a * 5 + b;
                    for (int c = 0; c <= 4; ++c) {
                        long mask = 0;
                        if (c >= a + b) {
                            int remaining = c - a - b;
                            for (int usePair = 0; usePair <= 1; ++usePair) {
                                if (usePair == 1 && p == 1)
                                    continue;
                                if (usePair == 1 && remaining < 2)
                                    continue;
                                int rem2 = remaining - 2 * usePair;
                                for (int q = 0; q <= 4; ++q) {
                                    if (q > rem2)
                                        break;
                                    if ((rem2 - q) % 3 != 0)
                                        continue;
                                    int ns = (p | usePair) * 25 + q * 5 + a;
                                    mask |= (1L << ns);
                                }
                            }
                        }
                        nfa[sid][c] = mask;
                    }
                }
            }
        }

        long startMask = 1L << 0;
        HashMap<Long, Integer> index = new HashMap<>();
        List<Long> masks = new ArrayList<>();
        Queue<Long> q = new LinkedList<>();

        index.put(startMask, 0);
        masks.add(startMask);
        q.add(startMask);

        List<int[]> trans = new ArrayList<>();

        while (!q.isEmpty()) {
            long mask = q.poll();
            int cur = index.get(mask);
            if (cur >= trans.size()) {
                trans.add(new int[5]);
            }
            for (int c = 0; c <= 4; ++c) {
                long nextMask = 0;
                long tmp = mask;
                while (tmp != 0) {
                    int i = Long.numberOfTrailingZeros(tmp);
                    tmp &= tmp - 1;
                    nextMask |= nfa[i][c];
                }

                int nxt;
                if (!index.containsKey(nextMask)) {
                    nxt = index.size();
                    index.put(nextMask, nxt);
                    masks.add(nextMask);
                    q.add(nextMask);
                } else {
                    nxt = index.get(nextMask);
                }
                trans.get(cur)[c] = nxt;
            }
        }

        long acc0Bit = 1L << 0;
        long acc1Bit = 1L << 25;

        List<Integer> accept0List = new ArrayList<>();
        List<Integer> accept1List = new ArrayList<>();
        for (int i = 0; i < masks.size(); ++i) {
            if ((masks.get(i) & acc0Bit) != 0)
                accept0List.add(i);
            if ((masks.get(i) & acc1Bit) != 0)
                accept1List.add(i);
        }

        DFA dfa = new DFA();
        dfa.trans = trans.toArray(new int[0][]);
        dfa.accept0 = accept0List.stream().mapToInt(i -> i).toArray();
        dfa.accept1 = accept1List.stream().mapToInt(i -> i).toArray();
        return dfa;
    }

    static class MahjongCounter {
        int maxT, maxTiles, maxLen, maxBlocks, stride;
        DFA dfa;
        int[] fact, invFact;
        List<Block> tripleBlocks = new ArrayList<>();
        List<Block> pairBlocks = new ArrayList<>();
        int[][] dp0;
        int[][] dp1;

        MahjongCounter(int t) {
            maxT = t;
            maxTiles = 3 * t + 2;
            maxLen = 3 * t + 2;
            maxBlocks = t + 1;
            stride = maxTiles + 1;
            dfa = buildDFA();

            buildFactorials();
            buildBlockCounts();
            buildBlockDP();
        }

        void buildFactorials() {
            fact = new int[maxBlocks + 1];
            invFact = new int[maxBlocks + 1];
            fact[0] = 1;
            for (int i = 1; i <= maxBlocks; ++i) {
                fact[i] = (int) ((fact[i - 1] * (long) i) % MOD);
            }
            invFact[maxBlocks] = (int) modPow(fact[maxBlocks], MOD - 2);
            for (int i = maxBlocks; i >= 1; --i) {
                invFact[i - 1] = (int) ((invFact[i] * (long) i) % MOD);
            }
        }

        int combSmall(long N, int k) {
            if (k < 0 || N < k)
                return 0;
            long res = 1;
            for (int i = 0; i < k; ++i) {
                long term = (N - i) % MOD;
                if (term < 0)
                    term += MOD;
                res = (res * term) % MOD;
            }
            res = (res * invFact[k]) % MOD;
            return (int) res;
        }

        void buildBlockCounts() {
            int S = dfa.trans.length;
            int size = S * stride;
            int[] cur = new int[size];
            int[] next = new int[size];

            cur[0] = 1;

            for (int L = 1; L <= maxLen; ++L) {
                Arrays.fill(next, 0);
                for (int s = 0; s < S; ++s) {
                    int base = s * stride;
                    for (int m = 0; m <= maxTiles; ++m) {
                        int val = cur[base + m];
                        if (val == 0)
                            continue;
                        for (int c = 1; c <= 4; ++c) {
                            int nm = m + c;
                            if (nm > maxTiles)
                                break;
                            int ns = dfa.trans[s][c];
                            int idx = ns * stride + nm;
                            int v = next[idx] + val;
                            if (v >= MOD)
                                v -= MOD;
                            next[idx] = v;
                        }
                    }
                }

                int[] sum0 = new int[maxTiles + 1];
                int[] sum1 = new int[maxTiles + 1];

                for (int s : dfa.accept0) {
                    int base = s * stride;
                    for (int m = 0; m <= maxTiles; ++m) {
                        int v = sum0[m] + next[base + m];
                        if (v >= MOD)
                            v -= MOD;
                        sum0[m] = v;
                    }
                }
                for (int s : dfa.accept1) {
                    int base = s * stride;
                    for (int m = 0; m <= maxTiles; ++m) {
                        int v = sum1[m] + next[base + m];
                        if (v >= MOD)
                            v -= MOD;
                        sum1[m] = v;
                    }
                }

                for (int M = 0; M <= maxTiles; ++M) {
                    if (sum0[M] > 0 && M % 3 == 0)
                        tripleBlocks.add(new Block(L, M, sum0[M]));
                    if (sum1[M] > 0 && M % 3 == 2)
                        pairBlocks.add(new Block(L, M, sum1[M]));
                }

                int[] temp = cur;
                cur = next;
                next = temp;
            }
        }

        void convolveAdd(int[] dp, List<Block> blocks, int[] out) {
            for (Block b : blocks) {
                int Llimit = maxLen - b.len;
                int Mlimit = maxTiles - b.tiles;
                for (int L = 0; L <= Llimit; ++L) {
                    int base = L * stride;
                    int outBase = (L + b.len) * stride + b.tiles;
                    for (int M = 0; M <= Mlimit; ++M) {
                        int val = dp[base + M];
                        if (val == 0)
                            continue;
                        int idx = outBase + M;
                        out[idx] = (int) ((out[idx] + (long) val * b.count) % MOD);
                    }
                }
            }
        }

        void buildBlockDP() {
            int size = (maxLen + 1) * stride;
            dp0 = new int[maxBlocks + 1][size];
            dp1 = new int[maxBlocks + 1][size];
            dp0[0][0] = 1;

            for (int k = 0; k < maxBlocks; ++k) {
                convolveAdd(dp0[k], tripleBlocks, dp0[k + 1]);
                convolveAdd(dp1[k], tripleBlocks, dp1[k + 1]);
                convolveAdd(dp0[k], pairBlocks, dp1[k + 1]);
            }
        }

        long[] polyMul(long[] a, long[] b, int t) {
            long[] res = new long[t + 1];
            for (int i = 0; i <= Math.min(t, a.length - 1); ++i) {
                if (a[i] == 0)
                    continue;
                for (int j = 0; j <= Math.min(t - i, b.length - 1); ++j) {
                    if (b[j] == 0)
                        continue;
                    res[i + j] = (res[i + j] + a[i] * b[j]) % MOD;
                }
            }
            return res;
        }

        long[] polyPow(long[] base, long exp, int t) {
            long[] res = new long[t + 1];
            res[0] = 1;
            while (exp > 0) {
                if ((exp & 1) != 0)
                    res = polyMul(res, base, t);
                exp >>= 1;
                if (exp > 0)
                    base = polyMul(base, base, t);
            }
            return res;
        }

        long solve(long n, long s, int t) {
            if (s == 0 || t > maxT)
                return 0;

            long[] A = new long[maxTiles + 1];
            long[] B = new long[maxTiles + 1];

            for (int k = 0; k <= maxBlocks; ++k) {
                for (int L = 0; L <= maxLen; ++L) {
                    long N = n - L + 1;
                    if (N < k)
                        continue;
                    int comb = combSmall(N, k);
                    if (comb == 0)
                        continue;

                    int base = L * stride;
                    int[] dp0K = dp0[k];
                    int[] dp1K = dp1[k];

                    for (int M = 0; M <= maxTiles; ++M) {
                        int v0 = dp0K[base + M];
                        if (v0 > 0)
                            A[M] = (A[M] + (long) v0 * comb) % MOD;
                        int v1 = dp1K[base + M];
                        if (v1 > 0)
                            B[M] = (B[M] + (long) v1 * comb) % MOD;
                    }
                }
            }

            long[] G = new long[t + 1];
            long[] H = new long[t + 1];
            for (int k = 0; k <= t; ++k) {
                int idxG = 3 * k;
                int idxH = 3 * k + 2;
                if (idxG <= maxTiles)
                    G[k] = A[idxG];
                if (idxH <= maxTiles)
                    H[k] = B[idxH];
            }

            long[] Gpow = polyPow(G, s - 1, t);
            long total = 0;
            for (int i = 0; i <= t; ++i) {
                total = (total + H[i] * Gpow[t - i]) % MOD;
            }
            total = (total * (s % MOD)) % MOD;
            return total;
        }
    }

    public static String solve() {
        long n = 100000000L;
        long s = 100000000L;
        int t = 30;
        MahjongCounter mc = new MahjongCounter(t);
        return Long.toString(mc.solve(n, s, t));
    }

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