public class Euler860 {
    static final long MOD = 989898989L;

    static long FValue(int n) {
        int span = 4 * n + 4;
        int size = 2 * span + 1;
        int shift = span;

        long[] cur = new long[size];
        long[] nxt = new long[size];
        cur[shift] = 1;

        for (int step = 1; step <= n; ++step) {
            java.util.Arrays.fill(nxt, 0);
            int lo = shift - 4 * step;
            int hi = shift + 4 * step;

            for (int i = lo; i <= hi; ++i) {
                long v = cur[i - 4];
                v += cur[i + 4];
                if (v >= MOD)
                    v -= MOD;
                v += cur[i - 1];
                if (v >= MOD)
                    v -= MOD;
                v += cur[i + 1];
                if (v >= MOD)
                    v -= MOD;
                nxt[i] = v;
            }

            long[] temp = cur;
            cur = nxt;
            nxt = temp;
        }

        return cur[shift];
    }

    public static String solve() {
        return Long.toString(FValue(9898));
    }

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