import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Euler365 {

    static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }

    static List<Integer> primesBetween(int loExclusive, int hiExclusive) {
        boolean[] isPrime = new boolean[hiExclusive];
        for (int i = 0; i < hiExclusive; i++)
            isPrime[i] = true;
        if (hiExclusive > 0)
            isPrime[0] = false;
        if (hiExclusive > 1)
            isPrime[1] = false;
        for (int p = 2; p * p < hiExclusive; p++) {
            if (isPrime[p]) {
                for (int q = p * p; q < hiExclusive; q += p) {
                    isPrime[q] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        int start = Math.max(2, loExclusive + 1);
        for (int x = start; x < hiExclusive; x++) {
            if (isPrime[x])
                primes.add(x);
        }
        return primes;
    }

    static int binomModPrimeLucas(long n, long k, int p) {
        int[] fact = new int[p];
        fact[0] = 1;
        for (int i = 1; i < p; i++) {
            fact[i] = (int) (((long) fact[i - 1] * i) % p);
        }

        int[] invFact = new int[p];
        invFact[p - 1] = (int) modPow(fact[p - 1], p - 2, p);
        for (int i = p - 1; i >= 1; i--) {
            invFact[i - 1] = (int) (((long) invFact[i] * i) % p);
        }

        long nn = n;
        long kk = k;
        long result = 1;
        while (nn > 0 || kk > 0) {
            int ni = (int) (nn % p);
            int ki = (int) (kk % p);
            if (ki > ni)
                return 0;

            long term = fact[ni];
            term = (term * invFact[ki]) % p;
            term = (term * invFact[ni - ki]) % p;
            result = (result * term) % p;

            nn /= p;
            kk /= p;
        }
        return (int) result;
    }

    static BigInteger sumCrtBinomOverTriples(long n, long k, List<Integer> primes) {
        int m = primes.size();
        int[] residues = new int[m];
        for (int i = 0; i < m; i++) {
            residues[i] = binomModPrimeLucas(n, k, primes.get(i));
        }

        int[][] inv = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (i == j)
                    continue;
                int mod = primes.get(j);
                inv[i][j] = (int) modPow(primes.get(i) % mod, mod - 2, mod);
            }
        }

        BigInteger total = BigInteger.ZERO;
        for (int i = 0; i < m - 2; i++) {
            long p = primes.get(i);
            long a = residues[i];
            for (int j = i + 1; j < m - 1; j++) {
                long q = primes.get(j);
                long b = residues[j];

                long diffAB = (b - a + q) % q;
                long t = (diffAB * inv[i][j]) % q;
                long xPq = a + p * t;
                long pq = p * q;

                for (int kidx = j + 1; kidx < m; kidx++) {
                    long r = primes.get(kidx);
                    long c = residues[kidx];

                    long diffC = (c - (xPq % r) + r) % r;
                    long invPqModR = ((long) inv[i][kidx] * inv[j][kidx]) % r;
                    long u = (diffC * invPqModR) % r;
                    long xVal = xPq + pq * u;

                    total = total.add(BigInteger.valueOf(xVal));
                }
            }
        }
        return total;
    }

    static String solve() {
        List<Integer> primes = primesBetween(1000, 5000);
        return sumCrtBinomOverTriples(1000000000000000000L, 1000000000L, primes).toString();
    }

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