import java.util.*;

public class Euler929 {

    static final long kMod = 1111124111L;

    static class NttMod {
        long mod;
        long primitiveRoot;

        NttMod(long m, long r) {
            mod = m;
            primitiveRoot = r;
        }
    }

    static final NttMod[] kNttMods = {
            new NttMod(998244353L, 3L),
            new NttMod(1004535809L, 3L),
            new NttMod(469762049L, 3L)
    };

    static long modPow(long a, long e, long mod) {
        long r = 1 % mod;
        a %= mod;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (r * a) % mod;
            a = (a * a) % mod;
            e >>= 1;
        }
        return r;
    }

    static long modInvPrime(long a, long mod) {
        return modPow(a, mod - 2, mod);
    }

    static void ntt(long[] a, long mod, long primitiveRoot, boolean invert) {
        int n = a.length;
        int j = 0;
        for (int i = 1; i < n; i++) {
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1)
                j ^= bit;
            j ^= bit;
            if (i < j) {
                long temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        for (int len = 2; len <= n; len <<= 1) {
            long wlen = modPow(primitiveRoot, (mod - 1) / len, mod);
            if (invert)
                wlen = modInvPrime(wlen, mod);

            long step = wlen;
            for (int i = 0; i < n; i += len) {
                long w = 1;
                for (int k = 0; k < len / 2; k++) {
                    long u = a[i + k];
                    long v = (a[i + k + len / 2] * w) % mod;
                    long x = u + v;
                    if (x >= mod)
                        x -= mod;
                    long y = u - v;
                    if (y < 0)
                        y += mod;
                    a[i + k] = x;
                    a[i + k + len / 2] = y;
                    w = (w * step) % mod;
                }
            }
        }

        if (invert) {
            long nInv = modInvPrime(n, mod);
            for (int i = 0; i < n; i++) {
                a[i] = (a[i] * nInv) % mod;
            }
        }
    }

    static long[] convolutionSingleMod(long[] a, long[] b, long mod, long primitiveRoot) {
        if (a.length == 0 || b.length == 0)
            return new long[0];

        if (Math.min(a.length, b.length) <= 64) {
            long[] out = new long[a.length + b.length - 1];
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < b.length; j++) {
                    out[i + j] = (out[i + j] + (a[i] * b[j]) % mod) % mod;
                }
            }
            return out;
        }

        int n = 1;
        int targetLen = a.length + b.length - 1;
        while (n < targetLen)
            n <<= 1;

        long[] fa = new long[n];
        long[] fb = new long[n];
        for (int i = 0; i < a.length; i++)
            fa[i] = a[i] % mod;
        for (int i = 0; i < b.length; i++)
            fb[i] = b[i] % mod;

        ntt(fa, mod, primitiveRoot, false);
        ntt(fb, mod, primitiveRoot, false);

        for (int i = 0; i < n; i++) {
            fa[i] = (fa[i] * fb[i]) % mod;
        }

        ntt(fa, mod, primitiveRoot, true);
        return Arrays.copyOf(fa, targetLen);
    }

    static long[] convolutionMod(long[] a, long[] b, long targetMod) {
        if (a.length == 0 || b.length == 0)
            return new long[0];

        long[][] convs = new long[3][];
        for (int t = 0; t < 3; t++) {
            convs[t] = convolutionSingleMod(a, b, kNttMods[t].mod, kNttMods[t].primitiveRoot);
        }

        long p1 = kNttMods[0].mod;
        long p2 = kNttMods[1].mod;
        long p3 = kNttMods[2].mod;

        long invP1ModP2 = modInvPrime(p1 % p2, p2);
        long p1ModP3 = p1 % p3;
        long p1P2ModP3 = (p1ModP3 * (p2 % p3)) % p3;
        long invP1P2ModP3 = modInvPrime(p1P2ModP3, p3);

        long p1ModM = p1 % targetMod;
        long p1P2ModM = (p1ModM * (p2 % targetMod)) % targetMod;

        long[] out = new long[convs[0].length];
        for (int i = 0; i < out.length; i++) {
            long r1 = convs[0][i];
            long r2 = convs[1][i];
            long r3 = convs[2][i];

            long t1 = r2 - r1;
            if (t1 < 0)
                t1 += p2;
            t1 = (t1 * invP1ModP2) % p2;

            long x12ModP3 = (r1 + p1ModP3 * t1) % p3;

            long t2 = r3 - x12ModP3;
            if (t2 < 0)
                t2 += p3;
            t2 = (t2 * invP1P2ModP3) % p3;

            long x = r1 % targetMod;
            x = (x + p1ModM * (t1 % targetMod)) % targetMod;
            x = (x + p1P2ModM * (t2 % targetMod)) % targetMod;
            out[i] = x;
        }

        return out;
    }

    static long[] polyInvOneMinus(long[] b, int n) {
        long[] inv = { 1 };
        int len = 1;
        while (len < n) {
            int m = Math.min(2 * len, n);
            long[] bCut = new long[m];
            for (int i = 0; i < m && i < b.length; i++) {
                bCut[i] = b[i] % kMod;
            }

            long[] prod = convolutionMod(inv, bCut, kMod);
            long[] nextProd = new long[m];
            for (int i = 0; i < m && i < prod.length; i++) {
                nextProd[i] = (kMod - prod[i]) % kMod;
            }
            nextProd[0] = (nextProd[0] + 2) % kMod;

            long[] nextInv = convolutionMod(inv, nextProd, kMod);
            inv = Arrays.copyOf(nextInv, m);
            len = m;
        }
        return Arrays.copyOf(inv, n);
    }

    static long[] buildA(int n) {
        long[] fib = new long[n + 1];
        if (n >= 1)
            fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
            if (fib[i] >= kMod)
                fib[i] -= kMod;
        }

        long[] a = new long[n + 1];
        for (int d = 1; d <= n; d++) {
            long b = fib[d];
            if ((d % 2) == 0) {
                b = (kMod - b) % kMod;
            }
            for (int m = d; m <= n; m += d) {
                a[m] += b;
                if (a[m] >= kMod)
                    a[m] -= kMod;
            }
        }
        return a;
    }

    static long solveFast(int n) {
        long[] a = buildA(n);
        long[] oneMinusA = new long[n + 1];
        oneMinusA[0] = 1;
        for (int i = 1; i <= n; i++) {
            oneMinusA[i] = (kMod - a[i]) % kMod;
        }

        long[] inv = polyInvOneMinus(oneMinusA, n + 1);
        return inv[n] % kMod;
    }

    public static String solve() {
        return Long.toString(solveFast(100000));
    }

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