import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ThreadLocalRandom;

public class Euler801 {
    static final long MOD = 993353399L;

    static boolean isPrime(long n) {
        if (n < 2)
            return false;
        long[] smallPrimes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
        for (long p : smallPrimes) {
            if (n == p)
                return true;
            if (n % p == 0)
                return false;
        }
        return BigInteger.valueOf(n).isProbablePrime(10);
    }

    static long pollardRho(long n) {
        if (n % 2 == 0)
            return 2;
        BigInteger bn = BigInteger.valueOf(n);
        ThreadLocalRandom rng = ThreadLocalRandom.current();
        while (true) {
            BigInteger c = BigInteger.valueOf(rng.nextLong(n - 3) + 2);
            BigInteger x = BigInteger.valueOf(rng.nextLong(n - 3) + 2);
            BigInteger y = x;
            long d = 1;

            while (d == 1) {
                x = x.multiply(x).add(c).mod(bn);
                y = y.multiply(y).add(c).mod(bn);
                y = y.multiply(y).add(c).mod(bn);
                BigInteger diff = x.subtract(y).abs();
                d = diff.gcd(bn).longValue();
            }
            if (d != n)
                return d;
        }
    }

    static void factorRec(long n, ArrayList<Long> out) {
        if (n == 1)
            return;
        if (isPrime(n)) {
            out.add(n);
            return;
        }
        long d = pollardRho(n);
        factorRec(d, out);
        factorRec(n / d, out);
    }

    static long modPow(long a, long e) {
        long r = 1 % MOD;
        a %= MOD;
        if (a < 0)
            a += MOD;
        while (e > 0) {
            if ((e & 1L) == 1) {
                r = (r * a) % MOD;
            }
            a = (a * a) % MOD;
            e >>= 1L;
        }
        return r;
    }

    static long fPrimeMod(long p) {
        long n = p - 1;
        ArrayList<Long> fac = new ArrayList<>();
        factorRec(n, fac);
        Collections.sort(fac);

        HashMap<Long, Integer> expo = new HashMap<>();
        for (long q : fac) {
            expo.put(q, expo.getOrDefault(q, 0) + 1);
        }

        long h = 1;
        for (Map.Entry<Long, Integer> entry : expo.entrySet()) {
            long q = entry.getKey();
            int e = entry.getValue();

            long qm = q % MOD;
            long qEMinus1 = modPow(qm, e - 1);
            long qE = modPow(qm, e);
            long qEPlus1 = modPow(qm, e + 1);

            long t = (qEPlus1 + qE - 1) % MOD;
            if (t < 0)
                t += MOD;

            long term = (qEMinus1 * t) % MOD;
            h = (h * term) % MOD;
        }

        long nm = n % MOD;
        long n2 = (nm * nm) % MOD;
        long nh = (nm * h) % MOD;

        long f = (n2 + nh) % MOD;
        if (f < 0)
            f += MOD;
        return f;
    }

    static ArrayList<Long> primesInRange(long lo, long hi) {
        ArrayList<Long> out = new ArrayList<>();
        if (hi < 2 || lo > hi)
            return out;
        if (lo <= 2 && 2 <= hi)
            out.add(2L);

        long start = lo <= 3 ? 3 : lo;
        if ((start & 1L) == 0L)
            start++;

        for (long x = start; x <= hi; x += 2) {
            if (isPrime(x))
                out.add(x);
        }
        return out;
    }

    static long SMod(long M, long N) {
        ArrayList<Long> primes = primesInRange(M, N);
        long ans = 0;
        for (long p : primes) {
            ans = (ans + fPrimeMod(p)) % MOD;
        }
        if (ans < 0)
            ans += MOD;
        return ans;
    }

    public static String solve() {
        return Long.toString(SMod(10000000000000000L, 10000000000000000L + 1000000L));
    }

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