public class Euler999 {
    private static final long MOD = 1_234_567_891L;
    private static final long INV2 = (MOD + 1) / 2;
    private static final long TARGET_N = 1_000_000_000_000_000_003L;

    private static long normalize(long value) {
        long result = value % MOD;
        return result < 0 ? result + MOD : result;
    }

    private static long subMod(long lhs, long rhs) {
        return lhs >= rhs ? lhs - rhs : lhs + MOD - rhs;
    }

    private static long mulMod(long lhs, long rhs) {
        return (lhs * rhs) % MOD;
    }

    private static long powMod(long base, long exponent) {
        long result = 1;
        while (exponent > 0) {
            if ((exponent & 1L) != 0) {
                result = mulMod(result, base);
            }
            base = mulMod(base, base);
            exponent >>= 1;
        }
        return result;
    }

    private static final class Field {
        final long[] c;

        Field(long c0) {
            this(c0, 0, 0, 0);
        }

        Field(long c0, long c1, long c2, long c3) {
            c = new long[] {normalize(c0), normalize(c1), normalize(c2), normalize(c3)};
        }

        boolean isBase() {
            return c[1] == 0 && c[2] == 0 && c[3] == 0;
        }

        boolean isRhoMultiple() {
            return c[0] == 0 && c[2] == 0 && c[3] == 0;
        }

        Field subtract(Field other) {
            return new Field(
                subMod(c[0], other.c[0]),
                subMod(c[1], other.c[1]),
                subMod(c[2], other.c[2]),
                subMod(c[3], other.c[3])
            );
        }

        Field negate() {
            return new Field(
                c[0] == 0 ? 0 : MOD - c[0],
                c[1] == 0 ? 0 : MOD - c[1],
                c[2] == 0 ? 0 : MOD - c[2],
                c[3] == 0 ? 0 : MOD - c[3]
            );
        }

        Field multiply(Field other) {
            long[] product = new long[7];
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 4; ++j) {
                    product[i + j] = (product[i + j] + mulMod(c[i], other.c[j])) % MOD;
                }
            }

            for (int i = 6; i >= 4; --i) {
                product[i - 4] = (product[i - 4] + 2 * product[i]) % MOD;
            }

            return new Field(product[0], product[1], product[2], product[3]);
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Field)) {
                return false;
            }
            Field other = (Field) obj;
            for (int i = 0; i < 4; ++i) {
                if (c[i] != other.c[i]) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public int hashCode() {
            int result = 17;
            for (long value : c) {
                result = 31 * result + Long.hashCode(value);
            }
            return result;
        }
    }

    private static final Field RHO = new Field(0, 1, 0, 0);
    private static final Field INV_RHO = new Field(0, 0, 0, INV2);

    private static Field square(Field value) {
        return value.multiply(value);
    }

    private static Field cube(Field value) {
        return value.multiply(value).multiply(value);
    }

    private static Field getValue(Field[] block, long center, long index) {
        long offset = index - center;
        if (offset < -4 || offset > 4) {
            throw new AssertionError("Block lookup out of range");
        }
        return block[(int) offset + 4];
    }

    private static Field oddValue(Field[] block, long center, long k) {
        return getValue(block, center, k + 1)
            .multiply(cube(getValue(block, center, k - 1)))
            .subtract(getValue(block, center, k - 2).multiply(cube(getValue(block, center, k))));
    }

    private static Field evenValue(Field[] block, long center, long k) {
        return getValue(block, center, k)
            .multiply(INV_RHO)
            .multiply(
                getValue(block, center, k + 2)
                    .multiply(square(getValue(block, center, k - 1)))
                    .subtract(
                        getValue(block, center, k - 2)
                            .multiply(square(getValue(block, center, k + 1)))
                    )
            );
    }

    private static long advance(Field[] block, long center, int bit) {
        Field[] previous = block.clone();
        long previousCenter = center;
        long nextCenter = 2 * center + bit;

        for (int offset = -4; offset <= 4; ++offset) {
            long index = nextCenter + offset;
            if ((index & 1L) == 0) {
                block[offset + 4] = evenValue(previous, previousCenter, index / 2);
            } else {
                block[offset + 4] = oddValue(previous, previousCenter, (index + 1) / 2);
            }
        }

        return nextCenter;
    }

    private static Field edsValue(long n) {
        if (n <= 0) {
            throw new AssertionError("Index must be positive");
        }

        Field[] block = {
            new Field(1),
            RHO.negate(),
            new Field(-1),
            new Field(0),
            new Field(1),
            RHO,
            new Field(-1),
            new Field(0, -2, 0, 0),
            new Field(-3)
        };
        long center = 1;

        int highest = 63 - Long.numberOfLeadingZeros(n);
        for (int bitIndex = highest - 1; bitIndex >= 0; --bitIndex) {
            center = advance(block, center, (int) ((n >> bitIndex) & 1L));
        }

        return block[4];
    }

    private static long sequenceValue(long n) {
        Field value = edsValue(n);
        if ((n & 1L) != 0) {
            if (!value.isBase()) {
                throw new AssertionError("Odd index should be in the base field");
            }
            if ((((n - 1) / 2) & 1L) == 0) {
                return value.c[0];
            }
            return value.c[0] == 0 ? 0 : MOD - value.c[0];
        }

        if (!value.isRhoMultiple()) {
            throw new AssertionError("Even index should be a rho multiple");
        }
        if ((((n - 2) / 2) & 1L) == 0) {
            return value.c[1];
        }
        return value.c[1] == 0 ? 0 : MOD - value.c[1];
    }

    private static long directValue(int n) {
        long[] a = new long[n + 5];
        a[1] = 1;
        a[2] = 1;
        a[3] = 1;
        a[4] = 2;

        for (int k = 3; k + 2 <= n; ++k) {
            long u = (k % 2 == 0) ? 1 : 2;
            long left = mulMod(a[k], a[k]);
            long right = mulMod(u, mulMod(a[k + 1], a[k - 1]));
            long denominator = a[k - 2];
            if (denominator == 0) {
                throw new AssertionError("Unexpected zero denominator");
            }
            a[k + 2] = mulMod(subMod(left, right), powMod(denominator, MOD - 2));
        }

        return a[n];
    }

    private static void check(boolean condition) {
        if (!condition) {
            throw new AssertionError();
        }
    }

    private static void runCheckpoints() {
        check(square(square(RHO)).equals(new Field(2)));
        for (int n = 1; n <= 200; ++n) {
            check(sequenceValue(n) == directValue(n));
        }
        check(sequenceValue(13) == 23_321);
        check(directValue(1003) == 231_906_014);
        check(sequenceValue(1003) == 231_906_014);
    }

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