Problem: Its Diwali time and little Roy thought of an interesting design for Rangoli.
He created an N x N grid. Roy fills some of the cells of grid with red color.

Cell located at ith row and jth column is colored if i+j is prime. Consider Zero-based numbering of grid. (See Sample Test Case Explanation for clarification)

Roy wants to know how many cells he will have to color given the size of grid N.

Input:

One integer indicating size of grid N

Output:

Print a single integer, number of cells Roy will have to color. Since answer can be very large output it modulo 1000000007

Constraints:

1 ≤ N ≤1000000

Sample Test Case Explanation:SAMPLE INPUT
3

SAMPLE OUTPUT
5

Explanation

As shown in the image above, five cells (0,2), (1,1), (1,2), (2,0), (2,1) are colored red because for (i,j) i+j for these cells results into a prime number.

Solution (in PYTHON):

Solution:
import math

'''
n = 9
8
i-(n-1)
max = 16
16-8 = 8
16 = 8+8 -> 1
15 = 7+8 = 8+7 2
14 3 6
13 4 5
8 5, 7 6, 6 7, 5 8

15 -> 16-15+1



'''

primes = {2: True, 3: True}
primesArray = [2,3]
largest = {"prm": 3}
n = int(raw_input())
size =  (n-1) * 2
m = 1000000007


def isPrime(n):
  if n%2 == 0:
    return False

  sqrt = int(math.sqrt(n))
  for i in primesArray:
    if i > sqrt: break
    if i == n : return True
    if n % i == 0: return False

  for i in range(largest["prm"], sqrt+1, 2):
    if n % i == 0: return False

  primes[n] = True
  primesArray.append(n)
  largest["prm"] = max(largest["prm"], n)
  return True

for i in range(3,size+1):
  isPrime(i)

count = 0
for i in range(2,size+1):
  if i in primes:
    if i <= n-1:
      count = (count + i + 1) % m
    if i > n-1:
      count = (count + size - i + 1) % m

print count