import java.util.*;

public class Euler529 {

    static final int kTargetSum = 10;
    static final int kDigits = 10;
    static final long kMod = 1000000007L;
    static final int kHistoryMask = (1 << (kTargetSum + 1)) - 1;

    static int encodeState(int history, int segment) {
        return history | (segment << 11);
    }

    static int highestBit(int mask) {
        return 31 - Integer.numberOfLeadingZeros(mask);
    }

    static class State {
        int history, segment;

        State(int h, int s) {
            history = h;
            segment = s;
        }
    }

    static State nextState(int history, int segment, int digit) {
        int delta = highestBit(segment);
        int newDelta = delta + digit;
        if (newDelta > kTargetSum)
            return null;
        int newSegment = segment | (1 << newDelta);
        if (((history >> (kTargetSum - newDelta)) & 1) == 1) {
            int shifted = (history << newDelta) & kHistoryMask;
            int newHistory = shifted;
            for (int k = 0; k <= newDelta; k++) {
                if (((newSegment >> k) & 1) == 1) {
                    newHistory |= (1 << (newDelta - k));
                }
            }
            return new State(newHistory, 1);
        } else {
            return new State(history, newSegment);
        }
    }

    static class RawAutomaton {
        int[][] trans;
        int[] accept;
        int start;
    }

    static RawAutomaton buildRaw() {
        List<State> states = new ArrayList<>();
        Map<Integer, Integer> index = new HashMap<>();

        State start = new State(1, 1);
        states.add(start);
        index.put(encodeState(1, 1), 0);

        for (int i = 0; i < states.size(); i++) {
            State cur = states.get(i);
            for (int d = 0; d < kDigits; d++) {
                State nxt = nextState(cur.history, cur.segment, d);
                if (nxt == null)
                    continue;
                int key = encodeState(nxt.history, nxt.segment);
                if (!index.containsKey(key)) {
                    index.put(key, states.size());
                    states.add(nxt);
                }
            }
        }

        int n = states.size();
        RawAutomaton raw = new RawAutomaton();
        raw.trans = new int[n][kDigits];
        raw.accept = new int[n];
        raw.start = 0;

        for (int i = 0; i < n; i++) {
            State cur = states.get(i);
            raw.accept[i] = (cur.segment == 1) ? 1 : 0;
            for (int d = 0; d < kDigits; d++) {
                State nxt = nextState(cur.history, cur.segment, d);
                if (nxt == null) {
                    raw.trans[i][d] = -1;
                } else {
                    raw.trans[i][d] = index.get(encodeState(nxt.history, nxt.segment));
                }
            }
        }
        return raw;
    }

    static class Automaton {
        int[][] trans;
        int[] accept;
        int start;
    }

    static Automaton minimizeAutomaton(RawAutomaton raw) {
        int n = raw.trans.length;
        int dead = n;
        int total = n + 1;

        int[][] trans = new int[total][kDigits];
        int[] accept = new int[total];
        for (int i = 0; i < n; i++) {
            accept[i] = raw.accept[i];
            for (int d = 0; d < kDigits; d++) {
                int t = raw.trans[i][d];
                trans[i][d] = (t == -1) ? dead : t;
            }
        }
        accept[dead] = 0;
        Arrays.fill(trans[dead], dead);

        List<List<Integer>>[] inv = new List[kDigits];
        for (int d = 0; d < kDigits; d++) {
            inv[d] = new ArrayList<>(total);
            for (int i = 0; i < total; i++)
                inv[d].add(new ArrayList<>());
        }
        for (int s = 0; s < total; s++) {
            for (int d = 0; d < kDigits; d++) {
                inv[d].get(trans[s][d]).add(s);
            }
        }

        List<List<Integer>> classes = new ArrayList<>();
        classes.add(new ArrayList<>());
        classes.add(new ArrayList<>());
        for (int s = 0; s < total; s++) {
            classes.get(accept[s] != 0 ? 0 : 1).add(s);
        }
        if (classes.get(0).isEmpty())
            classes.remove(0);
        else if (classes.size() == 2 && classes.get(1).isEmpty())
            classes.remove(1);

        int[] classOf = new int[total];
        for (int i = 0; i < classes.size(); i++) {
            for (int s : classes.get(i))
                classOf[s] = i;
        }

        Deque<Integer> work = new ArrayDeque<>();
        boolean[] inWork = new boolean[10000];
        for (int i = 0; i < classes.size(); i++) {
            work.add(i);
            inWork[i] = true;
        }

        boolean[] marked = new boolean[total];
        List<List<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < 10000; i++)
            bucket.add(new ArrayList<>());

        while (!work.isEmpty()) {
            int A = work.poll();
            inWork[A] = false;
            for (int d = 0; d < kDigits; d++) {
                List<Integer> X = new ArrayList<>();
                for (int t : classes.get(A)) {
                    for (int s : inv[d].get(t)) {
                        if (!marked[s]) {
                            marked[s] = true;
                            X.add(s);
                        }
                    }
                }
                if (X.isEmpty())
                    continue;

                List<Integer> touched = new ArrayList<>();
                for (int s : X) {
                    int c = classOf[s];
                    if (bucket.get(c).isEmpty())
                        touched.add(c);
                    bucket.get(c).add(s);
                }

                for (int c : touched) {
                    if (bucket.get(c).size() < classes.get(c).size()) {
                        List<Integer> inX = new ArrayList<>(bucket.get(c));
                        List<Integer> outX = new ArrayList<>();
                        for (int s : classes.get(c)) {
                            if (!marked[s])
                                outX.add(s);
                        }
                        classes.set(c, inX);
                        int newId = classes.size();
                        classes.add(outX);

                        for (int s : outX)
                            classOf[s] = newId;

                        if (inWork[c]) {
                            if (!inWork[newId]) {
                                work.add(newId);
                                inWork[newId] = true;
                            }
                        } else {
                            int pick = (classes.get(c).size() <= classes.get(newId).size()) ? c : newId;
                            if (!inWork[pick]) {
                                work.add(pick);
                                inWork[pick] = true;
                            }
                        }
                    }
                    bucket.get(c).clear();
                }
                for (int s : X)
                    marked[s] = false;
            }
        }

        Automaton min = new Automaton();
        min.trans = new int[classes.size()][kDigits];
        min.accept = new int[classes.size()];
        min.start = classOf[raw.start];

        for (int i = 0; i < classes.size(); i++) {
            int rep = classes.get(i).get(0);
            min.accept[i] = accept[rep];
            for (int d = 0; d < kDigits; d++) {
                min.trans[i][d] = classOf[trans[rep][d]];
            }
        }
        return min;
    }

    static long[] buildSequences(Automaton aut, int terms) {
        int n = aut.trans.length;
        List<Integer> acceptList = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (aut.accept[i] == 1)
                acceptList.add(i);

        long[] prefix = new long[terms + 1];
        long[] cur = new long[n];
        cur[aut.start] = 1;
        long[] nxt = new long[n];

        for (int i = 0; i < n; i++)
            nxt[i] = 0;
        for (int i = 0; i < n; i++) {
            if (cur[i] == 0)
                continue;
            for (int d = 1; d <= 9; d++) {
                int j = aut.trans[i][d];
                nxt[j] = (nxt[j] + cur[i]) % kMod;
            }
        }
        for (int i = 0; i < n; i++)
            cur[i] = nxt[i];

        long sum = 0;
        for (int idx : acceptList)
            sum = (sum + cur[idx]) % kMod;
        prefix[1] = sum;

        for (int len = 2; len <= terms; len++) {
            for (int i = 0; i < n; i++)
                nxt[i] = 0;
            for (int i = 0; i < n; i++) {
                if (cur[i] == 0)
                    continue;
                for (int d = 0; d <= 9; d++) {
                    int j = aut.trans[i][d];
                    nxt[j] = (nxt[j] + cur[i]) % kMod;
                }
            }
            for (int i = 0; i < n; i++)
                cur[i] = nxt[i];

            sum = 0;
            for (int idx : acceptList)
                sum = (sum + cur[idx]) % kMod;
            prefix[len] = (prefix[len - 1] + sum) % kMod;
        }
        return prefix;
    }

    static long modPow(long base, long exp) {
        long res = 1;
        long cur = base % kMod;
        while (exp > 0) {
            if ((exp & 1) == 1)
                res = (res * cur) % kMod;
            cur = (cur * cur) % kMod;
            exp >>= 1;
        }
        return res;
    }

    static List<Long> berlekampMassey(long[] seq) {
        List<Long> C = new ArrayList<>();
        C.add(1L);
        List<Long> B = new ArrayList<>();
        B.add(1L);
        int L = 0, m = 1;
        long b = 1;

        for (int n = 0; n < seq.length; n++) {
            long d = 0;
            for (int i = 0; i <= L; i++) {
                d = (d + C.get(i) * seq[n - i]) % kMod;
            }
            if (d == 0) {
                m++;
                continue;
            }
            List<Long> T = new ArrayList<>(C);
            long coef = (d * modPow(b, kMod - 2)) % kMod;
            while (C.size() < B.size() + m)
                C.add(0L);
            for (int i = 0; i < B.size(); i++) {
                long val = (C.get(i + m) - coef * B.get(i)) % kMod;
                if (val < 0)
                    val += kMod;
                C.set(i + m, val);
            }
            if (2 * L <= n) {
                L = n + 1 - L;
                B = T;
                b = d;
                m = 1;
            } else {
                m++;
            }
        }
        C.remove(0);
        for (int i = 0; i < C.size(); i++)
            C.set(i, (kMod - C.get(i)) % kMod);
        return C;
    }

    static long[] combinePoly(long[] a, long[] b, long[] coef) {
        int k = coef.length;
        long[] res = new long[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;
                res[i + j] = (res[i + j] + a[i] * b[j]) % kMod;
            }
        }
        for (int i = 2 * k - 2; i >= k; i--) {
            long val = res[i];
            if (val == 0)
                continue;
            for (int j = 0; j < k; j++) {
                res[i - 1 - j] = (res[i - 1 - j] + val * coef[j]) % kMod;
            }
        }
        return Arrays.copyOf(res, k);
    }

    static long linearRecurrence(long[] coef, long[] init, long n) {
        int k = coef.length;
        if (k == 0)
            return 0;
        if (n < init.length)
            return init[(int) n];
        if (k == 1)
            return (init[0] * modPow(coef[0], n)) % kMod;

        long[] pol = new long[k];
        pol[0] = 1;
        long[] e = new long[k];
        e[1] = 1;

        while (n > 0) {
            if ((n & 1) == 1)
                pol = combinePoly(pol, e, coef);
            e = combinePoly(e, e, coef);
            n >>= 1;
        }

        long res = 0;
        for (int i = 0; i < k; i++)
            res = (res + pol[i] * init[i]) % kMod;
        return res;
    }

    public static void main(String[] args) {
        RawAutomaton raw = buildRaw();
        Automaton aut = minimizeAutomaton(raw);
        int terms = 2 * aut.trans.length + 5;
        long[] prefix = buildSequences(aut, terms);

        List<Long> coefList = berlekampMassey(prefix);
        long[] coef = new long[coefList.size()];
        for (int i = 0; i < coef.length; i++)
            coef[i] = coefList.get(i);

        long[] init = Arrays.copyOf(prefix, coef.length);
        long answer = linearRecurrence(coef, init, 1000000000000000000L);
        System.out.println(answer);
    }
}