public class Euler892 {
    static final long kMod = 1234567891L;

    static int[] buildInverses(int limit) {
        int[] inv = new int[limit + 1];
        if (limit >= 1)
            inv[1] = 1;
        for (int i = 2; i <= limit; ++i) {
            inv[i] = (int) (kMod - (kMod / i) * inv[(int) (kMod % i)] % kMod);
        }
        return inv;
    }

    static long nextD(int n, long d_n, long d_n1, int[] inv) {
        long n2 = ((long) n * n) % kMod;
        long n1 = n + 1;

        long term1 = (n2 * n1) % kMod;
        term1 = (term1 * (2L * n + 3)) % kMod;
        term1 = (term1 * 16) % kMod;
        term1 = (term1 * d_n) % kMod;

        long quad = (2L * n2 + 4L * n + 3) % kMod;
        long term2 = (quad * d_n1) % kMod;
        term2 = (term2 * n1) % kMod;
        term2 = (term2 * 4) % kMod;

        long numerator = (term1 + term2) % kMod;

        long denomInv = ((long) inv[n] * inv[n + 2]) % kMod;
        denomInv = (denomInv * inv[n + 3]) % kMod;
        denomInv = (denomInv * inv[2 * n + 1]) % kMod;

        return (numerator * denomInv) % kMod;
    }

    public static String solve() {
        int target = 10000000;
        int invLimit = 2 * target + 3;
        int[] inv = buildInverses(invLimit);

        long dPrev = 0;
        long dCurr = 2;
        long total = 2;

        for (int n = 1; n + 2 <= target; ++n) {
            long dNext = nextD(n, dPrev, dCurr, inv);
            total += dNext;
            if (total >= kMod)
                total -= kMod;
            dPrev = dCurr;
            dCurr = dNext;
        }

        return Long.toString(total);
    }

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