public class Euler921 {

    static final long MOD = 398874989L;
    static final long GROUP = MOD * MOD - 1L;

    static class Elem {
        long a, b;

        Elem(long a, long b) {
            this.a = a;
            this.b = b;
        }
    }

    static long addMod(long x, long y, long mod) {
        long res = x + y;
        if (res >= mod)
            res -= mod;
        return res;
    }

    static long mulMod(long x, long y, long mod) {
        long res = 0;
        long a = x;
        long b = y;
        while (b > 0) {
            if ((b & 1L) != 0) {
                res = addMod(res, a, mod);
            }
            a = addMod(a, a, mod);
            b >>= 1L;
        }
        return res;
    }

    static Elem mulElem(Elem x, Elem y) {
        long aa = mulMod(x.a, y.a, MOD);
        long bb = mulMod(x.b, y.b, MOD);
        long real = addMod(aa, mulMod(5L, bb, MOD), MOD);
        long imag = addMod(mulMod(x.a, y.b, MOD), mulMod(x.b, y.a, MOD), MOD);
        return new Elem(real, imag);
    }

    static Elem[] precomputePowers(Elem base) {
        Elem[] powers = new Elem[64];
        powers[0] = base;
        for (int i = 1; i < 64; ++i) {
            powers[i] = mulElem(powers[i - 1], powers[i - 1]);
        }
        return powers;
    }

    static Elem powFromPowers(long exp, Elem[] powers) {
        Elem result = new Elem(1, 0);
        int bit = 0;
        while (exp != 0) {
            if ((exp & 1L) != 0) {
                result = mulElem(result, powers[bit]);
            }
            exp >>= 1L;
            bit++;
        }
        return result;
    }

    static long pow5Mod(long x) {
        long x2 = mulMod(x, x, MOD);
        long x4 = mulMod(x2, x2, MOD);
        return mulMod(x4, x, MOD);
    }

    static long sFromExp(long exp, Elem[] powers) {
        Elem value = powFromPowers(exp, powers);
        long p = value.b;
        long q = value.a == 0 ? 0 : MOD - value.a;
        return addMod(pow5Mod(p), pow5Mod(q), MOD);
    }

    public static String solve() {
        int kM = 1618034;
        Elem base = new Elem((MOD + MOD - 2) % MOD, 1);
        Elem[] basePowers = precomputePowers(base);

        long expPrev2 = 5;
        long expPrev1 = 5;

        long answer = sFromExp(expPrev1, basePowers);
        for (int i = 3; i <= kM; ++i) {
            long current = mulMod(expPrev1, expPrev2, GROUP);
            answer = addMod(answer, sFromExp(current, basePowers), MOD);
            expPrev2 = expPrev1;
            expPrev1 = current;
        }

        return Long.toString(answer);
    }

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