public class Euler895 {
    static final long MOD = 989898989L;

    static long normMod(long x) {
        x %= MOD;
        if (x < 0)
            x += MOD;
        return x;
    }

    static long addMod(long a, long b) {
        long v = a + b;
        if (v >= MOD)
            v -= MOD;
        return v;
    }

    static long subMod(long a, long b) {
        long v = a - b;
        if (v < 0)
            v += MOD;
        return v;
    }

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

    static long modPow(long base, long exp) {
        long result = 1;
        long cur = normMod(base);
        while (exp > 0) {
            if ((exp & 1) == 1)
                result = mulMod(result, cur);
            cur = mulMod(cur, cur);
            exp >>= 1;
        }
        return result;
    }

    static long modInv(long a) {
        return modPow(a, MOD - 2);
    }

    static long g8(long n, long inv3) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        long coeff = (n % 2 == 0) ? 14 : 20;
        long term1 = mulMod(coeff, mulMod(modPow(2, n / 2), inv3));
        long term2 = normMod(6 * n - 15);
        return addMod(term1, term2);
    }

    static long computeG(int n) {
        if (n <= 1)
            return 0;

        long inv3 = modInv(3);
        long pow2 = modPow(2, n / 2);
        long pref = (n % 2 == 0) ? 35 : 50;
        long counter = mulMod(pref, mulMod(pow2, inv3));
        counter = subMod(counter, normMod(6L * n));
        counter = subMod(counter, mulMod(35, inv3));

        int lim = (n - 1) / 2;
        long[] nums = new long[lim + 1];
        nums[0] = 1;
        if (lim >= 1)
            nums[1] = 10;

        for (int i = 2; i <= lim; ++i) {
            long a = mulMod(normMod(20L * i - 10), nums[i - 1]);
            long b = mulMod(normMod(64L * i - 64), nums[i - 2]);
            long val = subMod(a, b);
            nums[i] = mulMod(val, modInv(i));
        }

        for (int i = 0; i <= lim; ++i) {
            counter = addMod(counter, mulMod(nums[i], g8(n - 2L * i, inv3)));
        }
        return counter;
    }

    public static String solve() {
        return Long.toString(computeG(9898));
    }

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