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

public class Euler992 {
    private static final int MOD = 987_898_789;
    private static final int TARGET_N = 500;
    private static final int[] K_VALUES = {1, 10, 100, 1000, 10000};

    private static final class State {
        private final int position;
        private final int[] counts;

        private State(int position, int[] counts) {
            this.position = position;
            this.counts = counts.clone();
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!(other instanceof State)) {
                return false;
            }
            State rhs = (State) other;
            return position == rhs.position && Arrays.equals(counts, rhs.counts);
        }

        @Override
        public int hashCode() {
            return 31 * Integer.hashCode(position) + Arrays.hashCode(counts);
        }
    }

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

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

    private static int[][] buildNeededBinomials(int n, int[] kValues) {
        int maxRow = 0;
        for (int k : kValues) {
            maxRow = Math.max(maxRow, k + n - 2);
        }

        boolean[] needed = new boolean[maxRow + 1];
        for (int k : kValues) {
            for (int row = k; row <= k + n - 2; ++row) {
                needed[row] = true;
            }
        }

        int[][] rows = new int[maxRow + 1][];
        int[] current = new int[maxRow + 1];
        current[0] = 1;

        for (int row = 1; row <= maxRow; ++row) {
            current[row] = 1;
            for (int col = row - 1; col >= 1; --col) {
                current[col] = modAdd(current[col], current[col - 1]);
            }
            if (needed[row]) {
                rows[row] = Arrays.copyOf(current, row + 1);
            }
        }

        return rows;
    }

    private static int solveEndpoint(int n, int k, int endpoint, int[][] binomials) {
        int rightCrossings = k - (endpoint == 0 ? 1 : 0);
        int ways = 1;

        for (int stone = 1; stone < n; ++stone) {
            int row = k + stone - 1;
            if (rightCrossings <= 0 || rightCrossings > row + 1) {
                return 0;
            }
            ways = modMul(ways, binomials[row][rightCrossings - 1]);
            rightCrossings = k + stone - rightCrossings + (endpoint > stone ? 1 : 0);
        }

        return ways;
    }

    private static int solve(int n, int k, int[][] binomials) {
        int total = 0;
        for (int endpoint = 0; endpoint <= n; ++endpoint) {
            total = modAdd(total, solveEndpoint(n, k, endpoint, binomials));
        }
        return total;
    }

    private static long bruteForceDfs(
        int position,
        int[] counts,
        int[] target,
        int n,
        Map<State, Long> memo
    ) {
        State state = new State(position, counts);
        Long cached = memo.get(state);
        if (cached != null) {
            return cached.longValue();
        }

        boolean complete = true;
        for (int i = 0; i < n; ++i) {
            if (counts[i] > target[i]) {
                return 0L;
            }
            if (counts[i] != target[i]) {
                complete = false;
            }
        }

        if (complete) {
            long total = 1L + (position == n - 1 ? 1L : 0L);
            memo.put(state, total);
            return total;
        }

        long total = 0L;
        int[] nexts = {position - 1, position + 1};
        for (int next : nexts) {
            if (next < 0 || next > n) {
                continue;
            }
            if (next < n) {
                counts[next] += 1;
                if (counts[next] <= target[next]) {
                    total += bruteForceDfs(next, counts, target, n, memo);
                }
                counts[next] -= 1;
            } else {
                total += bruteForceDfs(next, counts, target, n, memo);
            }
        }

        memo.put(state, total);
        return total;
    }

    private static long bruteForce(int n, int k) {
        int[] target = new int[n];
        for (int i = 0; i < n; ++i) {
            target[i] = k + i;
        }

        int[] counts = new int[n];
        counts[0] = 1;
        return bruteForceDfs(0, counts, target, n, new HashMap<>());
    }

    private static void runCheckpoints(int[][] binomials) {
        for (int n = 1; n <= 6; ++n) {
            for (int k = 1; k <= 3; ++k) {
                if ((long) solve(n, k, binomials) != bruteForce(n, k)) {
                    throw new IllegalStateException("Checkpoint failed for n=" + n + ", k=" + k);
                }
            }
        }

        if (solve(3, 2, binomials) != 17) {
            throw new IllegalStateException("Checkpoint failed for W(3,2)");
        }
        if (solve(6, 1, binomials) != 1320) {
            throw new IllegalStateException("Checkpoint failed for W(6,1)");
        }
        if (solve(6, 5, binomials) != 16_793_280) {
            throw new IllegalStateException("Checkpoint failed for W(6,5)");
        }
    }

    private static int solveTarget(int[][] binomials) {
        int total = 0;
        for (int k : K_VALUES) {
            total = modAdd(total, solve(TARGET_N, k, binomials));
        }
        return total;
    }

    public static void main(String[] args) {
        boolean shouldRunCheckpoints = true;

        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                shouldRunCheckpoints = false;
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            System.exit(1);
        }

        int[][] binomials = buildNeededBinomials(TARGET_N, K_VALUES);

        if (shouldRunCheckpoints) {
            runCheckpoints(binomials);
        }

        System.out.println(solveTarget(binomials));
    }
}