import java.util.*;

public class Euler939 {

    static final int kMod = 1234567891;

    static int addMod(int a, int b) {
        long s = (long) a + b;
        if (s >= kMod)
            s -= kMod;
        return (int) s;
    }

    static int addMulMod(int a, int x, int y) {
        long prod = (long) x * (long) y;
        long s = (long) a + (prod % kMod);
        if (s >= kMod)
            s -= kMod;
        return (int) s;
    }

    public static String solve(int N) {
        int W = N + 1;

        int[][] part = new int[W][W];
        part[0][0] = 1;
        for (int u = 1; u <= N; ++u) {
            part[u][0] = 1;
            for (int v = 1; v <= N; ++v) {
                int val = part[u - 1][v];
                if (v >= u) {
                    val = addMod(val, part[u][v - u]);
                }
                part[u][v] = val;
            }
        }

        int[][] g = new int[W][W];
        for (int t = 0; t <= N; ++t) {
            for (int v = 0; v <= t; ++v) {
                g[t][v] = part[t - v][v];
            }
        }

        part = null;

        int[] agg = new int[W];
        int[] pref = new int[W];
        int contribGe2 = 0;

        for (int vA = 0; vA <= N; ++vA) {
            int addV = vA - 2;
            if (addV >= 0) {
                for (int t = addV; t <= N; ++t) {
                    agg[t] = addMod(agg[t], g[t][addV]);
                }
            }

            int run = 0;
            for (int t = 0; t <= N; ++t) {
                run = addMod(run, agg[t]);
                pref[t] = run;
            }

            for (int tA = vA; tA <= N; ++tA) {
                int ga = g[tA][vA];
                if (ga == 0)
                    continue;
                contribGe2 = addMulMod(contribGe2, ga, pref[N - tA]);
            }
        }

        int[] prefEven = new int[W];
        int[] prefOdd = new int[W];
        int contribEq1 = 0;

        for (int vA = 1; vA <= N; ++vA) {
            int vB = vA - 1;
            int evenSum = 0;
            int oddSum = 0;

            for (int t = 0; t <= N; ++t) {
                int gb = g[t][vB];
                if ((t & 1) != 0) {
                    oddSum = addMod(oddSum, gb);
                } else {
                    evenSum = addMod(evenSum, gb);
                }
                prefEven[t] = evenSum;
                prefOdd[t] = oddSum;
            }

            for (int tA = vA; tA <= N; ++tA) {
                int ga = g[tA][vA];
                if (ga == 0)
                    continue;
                int limit = N - tA;
                int waysB = ((tA & 1) != 0) ? prefOdd[limit] : prefEven[limit];
                contribEq1 = addMulMod(contribEq1, ga, waysB);
            }
        }

        int ans = addMod(contribGe2, contribEq1);
        return Integer.toString(ans);
    }

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