public class Euler854 {

    static final long MOD = 1234567891L;

    static long mulMod(long a, long b) {
        long aMod = a % MOD;
        long bMod = b % MOD;
        return (aMod * bMod) % MOD;
    }

    static long computeP(int n) {
        long ans = 1;
        if (n >= 3)
            ans = mulMod(ans, 2);

        int half = n / 2;
        long fPrev = 0, fCur = 1;
        long lPrev = 2, lCur = 1;

        for (int k = 1; k <= half; ++k) {
            long fk = (k == 1 ? 1 : 0);
            long lk = (k == 1 ? 1 : 0);

            if (k >= 2) {
                long fn = (fPrev + fCur) % MOD;
                fPrev = fCur;
                fCur = fn;
                fk = fCur;

                long ln = (lPrev + lCur) % MOD;
                lPrev = lCur;
                lCur = ln;
                lk = lCur;
            }

            if (k >= 2) {
                ans = mulMod(ans, ((k & 1) == 1) ? lk : fk);
            }
        }

        return ans;
    }

    public static String solve() {
        return Long.toString(computeP(1000000));
    }

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