public class Euler990 {
    private static final int MOD = 1_000_000_007;
    private static final int TARGET_N = 50;
    private static final int MAX_TERMS = (TARGET_N + 1) / 2;
    private static final int DELTA_LIMIT = 25;
    private static final int DELTA_SIZE = 2 * DELTA_LIMIT + 1;

    private static final class Options {
        boolean runCheckpoints = true;
        boolean allowMultithreading = true;
        int requestedThreads = 0;
        int targetN = TARGET_N;
    }

    private static final class IntList {
        private int[] data = new int[16];
        private int size = 0;

        void add(int value) {
            if (size == data.length) {
                int[] next = new int[data.length * 2];
                System.arraycopy(data, 0, next, 0, data.length);
                data = next;
            }
            data[size++] = value;
        }

        int[] toArray() {
            int[] result = new int[size];
            System.arraycopy(data, 0, result, 0, size);
            return result;
        }
    }

    private static final class Transition {
        final int[][] diffs = new int[10][];
        final int[][] ways = new int[10][];
    }

    private static int modAdd(int a, int b) {
        int s = a + b;
        return s >= MOD ? s - MOD : s;
    }

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

    private static int[] convolve(int[] lhs, int[] rhs) {
        int[] result = new int[lhs.length + rhs.length - 1];
        for (int i = 0; i < lhs.length; ++i) {
            int left = lhs[i];
            if (left == 0) {
                continue;
            }
            for (int j = 0; j < rhs.length; ++j) {
                int right = rhs[j];
                if (right == 0) {
                    continue;
                }
                result[i + j] = modAdd(result[i + j], modMul(left, right));
            }
        }
        return result;
    }

    private static int[] appendDigitSet(int[] poly, int lowDigit, int highDigit) {
        int[] next = new int[poly.length + highDigit];
        for (int i = 0; i < poly.length; ++i) {
            int coeff = poly[i];
            if (coeff == 0) {
                continue;
            }
            for (int digit = lowDigit; digit <= highDigit; ++digit) {
                next[i + digit] = modAdd(next[i + digit], coeff);
            }
        }
        return next;
    }

    private static final class Solver {
        private final int[][] binom;
        private final int[][][] digitSums;
        private final int[][][] transitionBase;
        private final int transitionCount;
        private final Transition[] transitions;

        Solver(Options options) {
            binom = buildBinom();
            digitSums = buildDigitSumPolynomials();
            transitionBase = new int[MAX_TERMS + 1][MAX_TERMS + 1][MAX_TERMS + 1];
            transitionCount = buildTransitionBase();
            transitions = buildTransitions();
        }

        private static int[][] buildBinom() {
            int[][] result = new int[MAX_TERMS + 1][MAX_TERMS + 1];
            result[0][0] = 1;
            for (int n = 1; n <= MAX_TERMS; ++n) {
                result[n][0] = 1;
                result[n][n] = 1;
                for (int k = 1; k < n; ++k) {
                    result[n][k] = result[n - 1][k - 1] + result[n - 1][k];
                }
            }
            return result;
        }

        private static int[][][] buildDigitSumPolynomials() {
            int[][][] result = new int[MAX_TERMS + 1][MAX_TERMS + 1][];
            int[][] freeDigits = new int[MAX_TERMS + 1][];
            int[][] leadingDigits = new int[MAX_TERMS + 1][];
            freeDigits[0] = new int[] {1};
            leadingDigits[0] = new int[] {1};

            for (int terms = 1; terms <= MAX_TERMS; ++terms) {
                freeDigits[terms] = appendDigitSet(freeDigits[terms - 1], 0, 9);
                leadingDigits[terms] = appendDigitSet(leadingDigits[terms - 1], 1, 9);
            }

            for (int active = 0; active <= MAX_TERMS; ++active) {
                for (int next = 0; next <= active; ++next) {
                    result[active][next] = convolve(leadingDigits[active - next], freeDigits[next]);
                }
            }
            return result;
        }

        private int buildTransitionBase() {
            int nextIndex = 0;
            for (int leftActive = 0; leftActive <= MAX_TERMS; ++leftActive) {
                for (int leftNext = 0; leftNext <= leftActive; ++leftNext) {
                    for (int rightActive = 0; rightActive + leftActive <= MAX_TERMS; ++rightActive) {
                        transitionBase[leftActive][leftNext][rightActive] = nextIndex;
                        nextIndex += rightActive + 1;
                    }
                }
            }
            return nextIndex;
        }

        private Transition buildSingleTransition(int leftActive, int leftNext, int rightActive, int rightNext) {
            Transition transition = new Transition();
            int[] leftPoly = digitSums[leftActive][leftNext];
            int[] rightPoly = digitSums[rightActive][rightNext];

            int minDiff = -rightPoly.length + 1;
            int maxDiff = leftPoly.length - 1;
            int[] diffCounts = new int[maxDiff - minDiff + 1];

            for (int leftSum = 0; leftSum < leftPoly.length; ++leftSum) {
                int leftWays = leftPoly[leftSum];
                if (leftWays == 0) {
                    continue;
                }
                for (int rightSum = 0; rightSum < rightPoly.length; ++rightSum) {
                    int rightWays = rightPoly[rightSum];
                    if (rightWays == 0) {
                        continue;
                    }
                    int diff = leftSum - rightSum;
                    diffCounts[diff - minDiff] =
                            modAdd(diffCounts[diff - minDiff], modMul(leftWays, rightWays));
                }
            }

            IntList[] diffLists = new IntList[10];
            IntList[] wayLists = new IntList[10];

            for (int diff = minDiff; diff <= maxDiff; ++diff) {
                int ways = diffCounts[diff - minDiff];
                if (ways == 0) {
                    continue;
                }
                int residue = ((diff % 10) + 10) % 10;
                if (diffLists[residue] == null) {
                    diffLists[residue] = new IntList();
                    wayLists[residue] = new IntList();
                }
                diffLists[residue].add(diff);
                wayLists[residue].add(ways);
            }

            for (int residue = 0; residue < 10; ++residue) {
                transition.diffs[residue] = diffLists[residue] == null ? new int[0] : diffLists[residue].toArray();
                transition.ways[residue] = wayLists[residue] == null ? new int[0] : wayLists[residue].toArray();
            }

            return transition;
        }

        private Transition[] buildTransitions() {
            Transition[] result = new Transition[transitionCount];
            for (int leftActive = 0; leftActive <= MAX_TERMS; ++leftActive) {
                for (int leftNext = 0; leftNext <= leftActive; ++leftNext) {
                    for (int rightActive = 0; rightActive + leftActive <= MAX_TERMS; ++rightActive) {
                        int base = transitionBase[leftActive][leftNext][rightActive];
                        for (int rightNext = 0; rightNext <= rightActive; ++rightNext) {
                            result[base + rightNext] =
                                    buildSingleTransition(leftActive, leftNext, rightActive, rightNext);
                        }
                    }
                }
            }
            return result;
        }

        int solve(int n) {
            assert 0 <= n && n <= TARGET_N;

            final int strideLen = (MAX_TERMS + 1) * (MAX_TERMS + 1) * DELTA_SIZE;
            final int strideA = (MAX_TERMS + 1) * DELTA_SIZE;
            final int strideB = DELTA_SIZE;

            int[] dp = new int[(n + 1) * strideLen];

            for (int leftTerms = 1; leftTerms <= MAX_TERMS; ++leftTerms) {
                for (int rightTerms = 1; rightTerms + leftTerms <= MAX_TERMS; ++rightTerms) {
                    int baseLength = leftTerms + rightTerms - 1;
                    if (baseLength > n) {
                        continue;
                    }
                    dp[index(baseLength, leftTerms, rightTerms, 0, strideLen, strideA, strideB)] = 1;
                }
            }

            for (int used = 0; used <= n; ++used) {
                for (int leftActive = 0; leftActive <= MAX_TERMS; ++leftActive) {
                    for (int rightActive = 0; rightActive + leftActive <= MAX_TERMS; ++rightActive) {
                        if (leftActive == 0 && rightActive == 0) {
                            continue;
                        }

                        int nextLength = used + leftActive + rightActive;
                        if (nextLength > n) {
                            continue;
                        }

                        for (int delta = -DELTA_LIMIT; delta <= DELTA_LIMIT; ++delta) {
                            int current =
                                    dp[index(used, leftActive, rightActive, delta, strideLen, strideA, strideB)];
                            if (current == 0) {
                                continue;
                            }

                            int residue = ((-delta) % 10 + 10) % 10;
                            for (int leftNext = 0; leftNext <= leftActive; ++leftNext) {
                                int chooseLeft = binom[leftActive][leftNext];
                                for (int rightNext = 0; rightNext <= rightActive; ++rightNext) {
                                    int structureWeight =
                                            modMul(current, modMul(chooseLeft, binom[rightActive][rightNext]));
                                    int tindex = transitionBase[leftActive][leftNext][rightActive] + rightNext;
                                    Transition transition = transitions[tindex];
                                    int[] diffs = transition.diffs[residue];
                                    int[] ways = transition.ways[residue];
                                    for (int i = 0; i < diffs.length; ++i) {
                                        int total = diffs[i] + delta;
                                        int nextDelta = total / 10;
                                        if (nextDelta < -DELTA_LIMIT || nextDelta > DELTA_LIMIT) {
                                            continue;
                                        }
                                        int target =
                                                index(nextLength, leftNext, rightNext, nextDelta, strideLen, strideA,
                                                        strideB);
                                        dp[target] = modAdd(dp[target], modMul(structureWeight, ways[i]));
                                    }
                                }
                            }
                        }
                    }
                }
            }

            int answer = 0;
            for (int used = 0; used <= n; ++used) {
                answer = modAdd(answer, dp[index(used, 0, 0, 0, strideLen, strideA, strideB)]);
            }
            return answer;
        }

        private static int index(
                int used,
                int leftActive,
                int rightActive,
                int delta,
                int strideLen,
                int strideA,
                int strideB) {
            return used * strideLen + leftActive * strideA + rightActive * strideB + delta + DELTA_LIMIT;
        }
    }

    private static void usage() {
        System.err.println(
                "Usage:\n"
                        + "  java Euler990 [n] [--skip-checkpoints] [--single-thread] [--threads=N]");
    }

    private static Options parseOptions(String[] args) {
        Options options = new Options();
        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                options.runCheckpoints = false;
                continue;
            }
            if ("--single-thread".equals(arg)) {
                options.allowMultithreading = false;
                options.requestedThreads = 1;
                continue;
            }
            if (arg.startsWith("--threads=")) {
                options.requestedThreads = Integer.parseInt(arg.substring(10));
                continue;
            }
            if (!arg.isEmpty() && arg.charAt(0) == '-') {
                usage();
                System.exit(1);
            }
            options.targetN = Integer.parseInt(arg);
        }

        if (options.targetN < 0 || options.targetN > TARGET_N) {
            System.err.println("n must satisfy 0 <= n <= " + TARGET_N + ".");
            System.exit(1);
        }

        return options;
    }

    private static void runCheckpoints(Solver solver) {
        assert solver.solve(0) == 0;
        assert solver.solve(1) == 0;
        assert solver.solve(2) == 0;
        assert solver.solve(3) == 9;
        assert solver.solve(5) == 171;
        assert solver.solve(7) == 4878;
    }

    public static void main(String[] args) {
        Options options = parseOptions(args);
        Solver solver = new Solver(options);
        if (options.runCheckpoints) {
            runCheckpoints(solver);
        }
        System.out.println(solver.solve(options.targetN));
    }
}