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

public class Euler492 {

    private static long modPow(long base, long exp, long mod) {
        if (mod == 1L)
            return 0L;
        long out = 1L % mod;
        base %= mod;
        while (exp > 0L) {
            if ((exp & 1L) != 0L) {
                out = mulMod(out, base, mod);
            }
            base = mulMod(base, base, mod);
            exp >>= 1L;
        }
        return out;
    }

    private static long modInvPrime(long a, long p) {
        return modPow(a, p - 2L, p);
    }

    private static long subMod(long a, long b, long p) {
        return (a >= b) ? (a - b) : (a + p - b);
    }

    private static long mulMod(long a, long b, long mod) {
        return ((a % mod) * (b % mod)) % mod;
    }

    private static List<Integer> simplePrimesUpTo(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++)
            isPrime[i] = true;

        for (long p = 2; p * p <= limit; ++p) {
            if (!isPrime[(int) p])
                continue;
            for (long x = p * p; x <= limit; x += p) {
                isPrime[(int) x] = false;
            }
        }

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

    private static List<Long> primesInSegment(long lo, long hi) {
        int root = (int) Math.sqrt(hi) + 1;
        List<Integer> basePrimes = simplePrimesUpTo(root);

        int len = (int) (hi - lo + 1);
        boolean[] isPrime = new boolean[len];
        for (int i = 0; i < len; i++)
            isPrime[i] = true;

        for (int p : basePrimes) {
            long start = (lo + p - 1) / p * p;
            if (start < (long) p * p)
                start = (long) p * p;
            for (long x = start; x <= hi; x += p) {
                isPrime[(int) (x - lo)] = false;
            }
        }

        if (lo == 0) {
            if (len > 0)
                isPrime[0] = false;
            if (len > 1)
                isPrime[1] = false;
        } else if (lo == 1) {
            if (len > 0)
                isPrime[0] = false;
        }

        List<Long> out = new ArrayList<>();
        for (long x = lo; x <= hi; ++x) {
            if (isPrime[(int) (x - lo)])
                out.add(x);
        }
        return out;
    }

    private static long lucasVMod(long k, long p, long P) {
        if (k == 0L)
            return 2L % p;

        long vm = 2L % p;
        long vmp1 = P % p;

        int msb = 63 - Long.numberOfLeadingZeros(k);
        for (int bit = msb; bit >= 0; --bit) {
            long v2m = subMod(mulMod(vm, vm, p), 2L % p, p);
            long v2m1 = subMod(mulMod(vm, vmp1, p), P % p, p);
            long v2m2 = subMod(mulMod(vmp1, vmp1, p), 2L % p, p);

            if (((k >> bit) & 1L) == 0L) {
                vm = v2m;
                vmp1 = v2m1;
            } else {
                vm = v2m1;
                vmp1 = v2m2;
            }
        }
        return vm;
    }

    private static long aNModP(long n, long p) {
        if (n == 1L)
            return 1L % p;

        long leg = modPow(117L % p, (p - 1L) / 2L, p);
        boolean residue = (leg == 1L);
        long orderMod = residue ? (p - 1L) : (p + 1L);

        long idx = modPow(2L, n - 1L, orderMod);
        long b = lucasVMod(idx, p, 11L);

        long inv6 = modInvPrime(6L, p);
        long a = mulMod(subMod(b, 5L % p, p), inv6, p);
        return a;
    }

    private static long B(long x, long y, long n) {
        long lo = x;
        long hi = x + y;
        List<Long> primes = primesInSegment(lo, hi);

        long total = 0L;
        for (long p : primes) {
            total += aNModP(n, p);
        }
        return total;
    }

    public static void main(String[] args) {
        long x = 1000000000L;
        long y = 10000000L;
        long n = 1000000000000000L;
        System.out.println(B(x, y, n));
    }
}