import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Euler544 {
    static final long MOD = 1000000007L;
    static final int MAX_DEG = 90;

    static long encodeState(int size, byte[] labels) {
        long key = size;
        for (int i = 0; i < size; i++) {
            key = (key << 4) | labels[i];
        }
        return key;
    }

    static byte[] decodeLabels(long key, int size) {
        byte[] labels = new byte[size];
        for (int i = size - 1; i >= 0; i--) {
            labels[i] = (byte) (key & 0xF);
            key >>= 4;
        }
        return labels;
    }

    static int decodeSize(long key, int originalSize) {
        return originalSize;
    }

    static class CanonicalResult {
        int size;
        int numLabels;
        long key;

        CanonicalResult(int size, int numLabels, long key) {
            this.size = size;
            this.numLabels = numLabels;
            this.key = key;
        }
    }

    static CanonicalResult canonicalize(int size, byte[] labels) {
        byte[] remap = new byte[16];
        Arrays.fill(remap, (byte) -1);
        byte next = 0;
        byte[] out = new byte[size];
        for (int i = 0; i < size; i++) {
            byte lbl = labels[i];
            if (remap[lbl] == -1)
                remap[lbl] = next++;
            out[i] = remap[lbl];
        }
        return new CanonicalResult(size, next, encodeState(size, out));
    }

    static void polyAdd(long[] dest, long[] src) {
        for (int i = 0; i <= MAX_DEG; i++) {
            dest[i] = (dest[i] + src[i]) % MOD;
        }
    }

    static void polySub(long[] dest, long[] src) {
        for (int i = 0; i <= MAX_DEG; i++) {
            dest[i] = (dest[i] - src[i] + MOD) % MOD;
        }
    }

    static long[] polyMulQ(long[] p) {
        long[] out = new long[MAX_DEG + 1];
        System.arraycopy(p, 0, out, 1, MAX_DEG);
        return out;
    }

    static class StateInfo {
        int size;
        int numLabels;
        long[] poly;

        StateInfo(int size, int numLabels, long[] poly) {
            this.size = size;
            this.numLabels = numLabels;
            this.poly = poly;
        }
    }

    static class StateMap {
        Map<Long, StateInfo> map = new HashMap<>();

        void addState(int size, int numLabels, long key, long[] p, boolean negate) {
            long[] pToAdd;
            if (negate) {
                pToAdd = new long[MAX_DEG + 1];
                for (int i = 0; i <= MAX_DEG; i++) {
                    pToAdd[i] = p[i] == 0 ? 0 : MOD - p[i];
                }
            } else {
                pToAdd = p;
            }

            StateInfo info = map.get(key);
            if (info == null) {
                map.put(key, new StateInfo(size, numLabels, pToAdd.clone()));
            } else {
                polyAdd(info.poly, pToAdd);
            }
        }
    }

    static StateMap addVertexEnd(StateMap cur) {
        StateMap out = new StateMap();
        for (Map.Entry<Long, StateInfo> entry : cur.map.entrySet()) {
            long key = entry.getKey();
            StateInfo info = entry.getValue();
            byte[] labels = decodeLabels(key, info.size);
            byte[] newLabels = Arrays.copyOf(labels, info.size + 1);
            newLabels[info.size] = (byte) info.numLabels;
            long newKey = encodeState(info.size + 1, newLabels);
            out.addState(info.size + 1, info.numLabels + 1, newKey, info.poly, false);
        }
        return out;
    }

    static StateMap addEdge(StateMap cur, int posA, int posB) {
        StateMap out = new StateMap();
        for (Map.Entry<Long, StateInfo> entry : cur.map.entrySet()) {
            long key = entry.getKey();
            StateInfo info = entry.getValue();
            out.addState(info.size, info.numLabels, key, info.poly, false);

            byte[] labels = decodeLabels(key, info.size);
            byte la = labels[posA];
            byte lb = labels[posB];
            if (la != lb) {
                for (int i = 0; i < info.size; i++) {
                    if (labels[i] == lb)
                        labels[i] = la;
                }
                CanonicalResult cr = canonicalize(info.size, labels);
                out.addState(cr.size, cr.numLabels, cr.key, info.poly, true);
            } else {
                out.addState(info.size, info.numLabels, key, info.poly, true);
            }
        }
        return out;
    }

    static StateMap removePosSwap(StateMap cur, int pos) {
        StateMap out = new StateMap();
        for (Map.Entry<Long, StateInfo> entry : cur.map.entrySet()) {
            long key = entry.getKey();
            StateInfo info = entry.getValue();
            byte[] labels = decodeLabels(key, info.size);
            byte label = labels[pos];
            boolean unique = true;
            for (int i = 0; i < info.size; i++) {
                if (i != pos && labels[i] == label) {
                    unique = false;
                    break;
                }
            }

            byte[] nsLabels = new byte[info.size - 1];
            for (int i = 0; i < info.size - 1; i++) {
                if (i == pos) {
                    nsLabels[i] = labels[info.size - 1];
                } else {
                    nsLabels[i] = labels[i];
                }
            }

            CanonicalResult cr = canonicalize(info.size - 1, nsLabels);
            long[] p = unique ? polyMulQ(info.poly) : info.poly;
            out.addState(cr.size, cr.numLabels, cr.key, p, false);
        }
        return out;
    }

    static StateMap removeLast(StateMap cur) {
        StateMap out = new StateMap();
        for (Map.Entry<Long, StateInfo> entry : cur.map.entrySet()) {
            long key = entry.getKey();
            StateInfo info = entry.getValue();
            byte[] labels = decodeLabels(key, info.size);
            int pos = info.size - 1;
            byte label = labels[pos];
            boolean unique = true;
            for (int i = 0; i < pos; i++) {
                if (labels[i] == label) {
                    unique = false;
                    break;
                }
            }

            byte[] nsLabels = Arrays.copyOf(labels, info.size - 1);
            CanonicalResult cr = canonicalize(info.size - 1, nsLabels);
            long[] p = unique ? polyMulQ(info.poly) : info.poly;
            out.addState(cr.size, cr.numLabels, cr.key, p, false);
        }
        return out;
    }

    static long[] chromaticPolyGrid(int rows, int cols) {
        if (rows > cols) {
            int temp = rows;
            rows = cols;
            cols = temp;
        }

        StateMap cur = new StateMap();
        long[] base = new long[MAX_DEG + 1];
        base[0] = 1;
        cur.addState(0, 0, encodeState(0, new byte[0]), base, false);

        int frontier = 0;
        for (int c = 0; c < cols; c++) {
            for (int r = 0; r < rows; r++) {
                cur = addVertexEnd(cur);
                frontier++;
                int newPos = frontier - 1;
                if (c > 0)
                    cur = addEdge(cur, r, newPos);
                if (r > 0)
                    cur = addEdge(cur, r - 1, newPos);
                if (c > 0) {
                    cur = removePosSwap(cur, r);
                    frontier--;
                }
            }
        }

        while (frontier > 0) {
            cur = removeLast(cur);
            frontier--;
        }

        for (StateInfo info : cur.map.values()) {
            if (info.size == 0)
                return info.poly;
        }
        return new long[MAX_DEG + 1];
    }

    static long lagrangeEval(long[] y, long x, long[] fact, long[] invFact) {
        int m = y.length - 1;
        if (x <= m)
            return y[(int) x];

        long[] prefix = new long[m + 2];
        long[] suffix = new long[m + 2];
        prefix[0] = 1;
        for (int i = 0; i <= m; i++) {
            long term = (x - i) % MOD;
            if (term < 0)
                term += MOD;
            prefix[i + 1] = (prefix[i] * term) % MOD;
        }
        suffix[m + 1] = 1;
        for (int i = m; i >= 0; i--) {
            long term = (x - i) % MOD;
            if (term < 0)
                term += MOD;
            suffix[i] = (suffix[i + 1] * term) % MOD;
        }

        long res = 0;
        for (int i = 0; i <= m; i++) {
            long num = (prefix[i] * suffix[i + 1]) % MOD;
            long denom = (invFact[i] * invFact[m - i]) % MOD;
            long term = (((y[i] * num) % MOD) * denom) % MOD;
            if ((m - i) % 2 != 0)
                term = MOD - term;
            res = (res + term) % MOD;
        }
        return res;
    }

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

    static long sumPows(int d, long n, long[] fact, long[] invFact) {
        if (n <= 0)
            return 0;
        if (d == 0)
            return n % MOD;
        int m = d + 1;
        long[] y = new long[m + 1];
        for (int i = 1; i <= m; i++) {
            y[i] = (y[i - 1] + powMod(i, d)) % MOD;
        }
        return lagrangeEval(y, n % MOD, fact, invFact);
    }

    static long computeS(long[] coeffs, int maxDeg, long n, long[] fact, long[] invFact) {
        long res = 0;
        for (int d = 0; d <= maxDeg; d++) {
            if (coeffs[d] == 0)
                continue;
            long sumVal = sumPows(d, n, fact, invFact);
            res = (res + coeffs[d] * sumVal) % MOD;
        }
        return res;
    }

    public static String solve() {
        long[] fact = new long[MAX_DEG + 3];
        long[] invFact = new long[MAX_DEG + 3];
        fact[0] = 1;
        for (int i = 1; i < fact.length; i++)
            fact[i] = (fact[i - 1] * i) % MOD;
        invFact[invFact.length - 1] = powMod(fact[fact.length - 1], MOD - 2);
        for (int i = invFact.length - 1; i > 0; i--) {
            invFact[i - 1] = (invFact[i] * i) % MOD;
        }

        int R = 9;
        int C = 10;
        long N = 1112131415L;

        long[] poly = chromaticPolyGrid(R, C);
        return Long.toString(computeS(poly, R * C, N, fact, invFact));
    }

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