import java.math.BigInteger;

public class Euler487 {
    public static String solve() {
        int k = 10000;
        long n = 1000000000000L;
        long pLo = 2000000000L, pHi = 2000002000L;
        long total = 0;
        for (long p = pLo; p <= pHi; p++) {
            if (!isPrime64(p))
                continue;
            total += sModPrime(k, n, p);
        }
        return String.valueOf(total);
    }

    static long sModPrime(int k, long n, long p) {
        int maxM = k + 2;
        long[] fac = new long[maxM + 1], ifac = new long[maxM + 1];
        fac[0] = 1;
        for (int i = 1; i <= maxM; i++)
            fac[i] = fac[i - 1] * i % p;
        ifac[maxM] = modPow(fac[maxM], p - 2, p);
        for (int i = maxM; i > 0; i--)
            ifac[i - 1] = ifac[i] * i % p;
        long fk = powerSumMod(k, n, p, fac, ifac);
        long fk1 = powerSumMod(k + 1, n, p, fac, ifac);
        long n1 = (n + 1) % p;
        long part = n1 * fk % p;
        return (part - fk1 + p) % p;
    }

    static long powerSumMod(int exp, long n, long p, long[] fac, long[] ifac) {
        int m = exp + 1;
        long[] y = new long[m + 1];
        for (int i = 1; i <= m; i++) {
            long pw = modPow(i, exp, p);
            y[i] = (y[i - 1] + pw) % p;
        }
        return lagrange(y, m, n % p, fac, ifac, p);
    }

    static long lagrange(long[] y, int m, long x, long[] fac, long[] ifac, long p) {
        if (x <= m)
            return y[(int) x];
        long[] pref = new long[m + 2], suf = new long[m + 2];
        pref[0] = 1;
        suf[m + 1] = 1;
        for (int i = 0; i <= m; i++)
            pref[i + 1] = pref[i] * ((x - i + p) % p) % p;
        for (int i = m; i >= 0; i--)
            suf[i] = suf[i + 1] * ((x - i + p) % p) % p;
        long out = 0;
        for (int i = 0; i <= m; i++) {
            long num = pref[i] * suf[i + 1] % p;
            long den = ifac[i] * ifac[m - i] % p;
            if ((m - i) % 2 != 0)
                den = (p - den) % p;
            out = (out + y[i] * num % p * den % p) % p;
        }
        return out;
    }

    static long modPow(long b, long e, long p) {
        b %= p;
        if (b < 0)
            b += p;
        long r = 1;
        while (e > 0) {
            if ((e & 1) != 0)
                r = BigInteger.valueOf(r).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(p)).longValue();
            b = BigInteger.valueOf(b).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(p)).longValue();
            e >>= 1;
        }
        return r;
    }

    static boolean isPrime64(long n) {
        if (n < 2)
            return false;
        for (long p : new long[] { 2, 3, 5, 7, 11, 13 }) {
            if (n % p == 0)
                return n == p;
        }
        long d = n - 1;
        int s = 0;
        while (d % 2 == 0) {
            d /= 2;
            s++;
        }
        for (long a : new long[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022L }) {
            if (a % n == 0)
                continue;
            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1)
                continue;
            boolean witness = true;
            for (int i = 1; i < s; i++) {
                x = BigInteger.valueOf(x).multiply(BigInteger.valueOf(x)).mod(BigInteger.valueOf(n)).longValue();
                if (x == n - 1) {
                    witness = false;
                    break;
                }
            }
            if (witness)
                return false;
        }
        return true;
    }

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