import java.util.ArrayList;

public class Euler812 {

    static final int MOD = 998244353;

    static int addmod(int a, int b) {
        int s = a + b;
        if (s >= MOD)
            s -= MOD;
        return s;
    }

    static int submod(int a, int b) {
        int s = a - b;
        if (s < 0)
            s += MOD;
        return s;
    }

    static int[] computePhi(int M) {
        int[] phi = new int[M + 1];
        for (int i = 0; i <= M; ++i)
            phi[i] = i;
        for (int i = 2; i <= M; ++i) {
            if (phi[i] == i) {
                for (int j = i; j <= M; j += i) {
                    phi[j] -= phi[j] / i;
                }
            }
        }
        return phi;
    }

    static int[] buildChain1(int n, int[] deg) {
        ArrayList<Integer> tailWeights = new ArrayList<>();
        long prefix = 0;
        for (long m = 4; m < deg.length; m *= 2) {
            int d = deg[(int) m];
            if (d > n)
                break;
            prefix += d;
            long t = prefix + 1;
            if (t > n)
                break;
            tailWeights.add((int) t);
        }

        int[] G = new int[n + 1];
        int[] H = new int[n + 1];
        G[0] = 1;
        H[0] = 1;

        for (int t : tailWeights) {
            for (int k = t; k <= n; ++k) {
                G[k] = addmod(G[k], G[k - t]);
            }
        }

        for (int t : tailWeights) {
            for (int k = t; k <= n; ++k) {
                H[k] = submod(H[k], H[k - t]);
            }
        }

        int inv2 = (MOD + 1) / 2;
        int[] S = new int[n + 1];
        for (int k = 0; k <= n; ++k) {
            long val = (long) G[k] + H[k];
            if (k > 0) {
                val += (long) G[k - 1] - H[k - 1];
            }
            val %= MOD;
            if (val < 0)
                val += MOD;
            S[k] = (int) ((val * inv2) % MOD);
        }

        for (int k = 1; k <= n; ++k) {
            S[k] = addmod(S[k], S[k - 1]);
        }
        for (int k = 2; k <= n; ++k) {
            S[k] = addmod(S[k], S[k - 2]);
        }

        return S;
    }

    static int computeS(int n) {
        int M = Math.max(100, 40 * n);
        int[] phi = computePhi(M);
        int[] deg = new int[M + 1];
        if (M >= 1)
            deg[1] = 1;
        if (M >= 2)
            deg[2] = 1;
        for (int m = 3; m <= M; ++m) {
            deg[m] = phi[m] / 2;
        }

        int[] dp = buildChain1(n, deg);

        for (int b = 3; b <= M; b += 2) {
            if (deg[b] > n)
                continue;
            long prefix = 0;
            long m = b;
            while (m <= M) {
                int d = deg[(int) m];
                if (d > n)
                    break;
                prefix += d;
                if (prefix > n)
                    break;
                int w = (int) prefix;
                for (int k = w; k <= n; ++k) {
                    dp[k] = addmod(dp[k], dp[k - w]);
                }
                m *= 2;
            }
        }

        return dp[n];
    }

    public static String solve() {
        return Integer.toString(computeS(10000));
    }

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