import java.util.stream.IntStream;

public class Euler976 {
    static final long MOD = 1234567891;

    static long power(long base, long exp) {
        long result = 1 % MOD;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }

    static class Comb {
        int maxn;
        long[] fact;
        long[] invfact;

        Comb(int maxn) {
            this.maxn = maxn;
            fact = new long[maxn + 1];
            invfact = new long[maxn + 1];

            fact[0] = 1;
            for (int i = 1; i <= maxn; i++) {
                fact[i] = (fact[i - 1] * i) % MOD;
            }

            invfact[maxn] = power(fact[maxn], MOD - 2);
            for (int i = maxn; i >= 1; i--) {
                invfact[i - 1] = (invfact[i] * i) % MOD;
            }
        }

        long nCk(int n, int k) {
            if (k < 0 || k > n)
                return 0;
            return (fact[n] * invfact[k] % MOD) * invfact[n - k] % MOD;
        }
    }

    static long solveNEqKDiv4(int N) {
        if (N % 4 != 0) {
            System.err.println("[FATAL] This solver expects N % 4 == 0");
            System.exit(1);
        }

        int No = N / 2;
        int Na = N / 4;
        int maxFac = 2 * N;

        Comb C = new Comb(maxFac);
        long inv2 = (MOD + 1) / 2;

        long totalEven = IntStream.rangeClosed(0, No).parallel().mapToLong(m -> {
            int k = 2 * m;
            int n = N + k - 1;
            return C.nCk(n, k);
        }).reduce(0, (a, b) -> (a + b) % MOD);

        long l1Raw = IntStream.rangeClosed(0, Na).parallel().mapToLong(r -> {
            long a = C.nCk(No, 2 * r);
            long b = C.nCk(3 * No - r, No - r);
            return (a * b) % MOD;
        }).reduce(0, (a, b) -> (a + b) % MOD);

        long l1 = (inv2 * l1Raw) % MOD;
        long l2 = (inv2 * C.nCk(5 * Na, No)) % MOD;

        long lostEven = (l1 + l2) % MOD;

        long woddRaw = IntStream.range(0, Na).parallel().mapToLong(r -> {
            long a = C.nCk(No, 2 * r + 1);
            long b = C.nCk(3 * No - 1 - r, No - 1 - r);
            return (a * b) % MOD;
        }).reduce(0, (a, b) -> (a + b) % MOD);

        long winOdd = (inv2 * woddRaw) % MOD;

        long ans = (totalEven - lostEven + winOdd) % MOD;
        if (ans < 0)
            ans += MOD;
        return ans;
    }

    public static String solve() {
        return Long.toString(solveNEqKDiv4(10_000_000));
    }

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