import java.util.ArrayList;
import java.util.List;

public class Euler304 {
    static List<Integer> sieveBasePrimes(int limit) {
        byte[] isPrime = new byte[limit + 1];
        for (int i = 2; i <= limit; ++i)
            isPrime[i] = 1;

        for (int p = 2; (long) p * p <= limit; ++p) {
            if (isPrime[p] == 1) {
                for (int q = p * p; q <= limit; q += p) {
                    isPrime[q] = 0;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int p = 2; p <= limit; ++p) {
            if (isPrime[p] == 1)
                primes.add(p);
        }
        return primes;
    }

    static List<Long> firstPrimesAfter(long start, int count) {
        int baseLimit = 11000000;
        List<Integer> basePrimes = sieveBasePrimes(baseLimit);

        int segmentSize = 4000000;
        List<Long> out = new ArrayList<>(count);

        long low = start + 1;
        byte[] isPrime = new byte[segmentSize];

        while (out.size() < count) {
            long high = low + segmentSize - 1;
            for (int i = 0; i < segmentSize; ++i)
                isPrime[i] = 1;

            for (int p : basePrimes) {
                long pp = (long) p;
                if (pp * pp > high)
                    break;

                long first = ((low + pp - 1) / pp) * pp;
                if (first < pp * pp) {
                    first = pp * pp;
                }

                int startIdx = (int) (first - low);
                for (int x = startIdx; x < segmentSize; x += p) {
                    isPrime[x] = 0;
                }
            }

            for (int i = 0; i < segmentSize && out.size() < count; ++i) {
                long value = low + i;
                if (value >= 2 && isPrime[i] == 1) {
                    out.add(value);
                }
            }

            low = high + 1;
        }

        return out;
    }

    static class Pair {
        long first, second;

        Pair(long first, long second) {
            this.first = first;
            this.second = second;
        }
    }

    static Pair fibPairMod(long n, long mod) {
        if (n == 0)
            return new Pair(0, 1 % mod);

        Pair half = fibPairMod(n >>> 1, mod);
        long a = half.first;
        long b = half.second;

        long twoB = (2L * b) % mod;

        long c = mulMod(a, (twoB + mod - a) % mod, mod);
        long d = (mulMod(a, a, mod) + mulMod(b, b, mod)) % mod;

        if ((n & 1) == 0) {
            return new Pair(c, d);
        }
        return new Pair(d, (c + d) % mod);
    }

    // multiply modulo handling overflow
    static long mulMod(long a, long b, long mod) {
        long res = 0;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res + a) % mod;
            }
            a = (a * 2) % mod;
            b >>>= 1;
        }
        return res;
    }

    public static String solve() {
        long start = 100000000000000L;
        int count = 100000;
        long mod = 1234567891011L;

        List<Long> primes = firstPrimesAfter(start, count);
        long sum = 0;
        for (long p : primes) {
            sum += fibPairMod(p, mod).first;
            if (sum >= mod)
                sum %= mod;
        }

        return String.valueOf(sum % mod);
    }

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