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:
from math import sqrt
mod=1000000007
a=input()
matrix=a*a
n=a-1
def sieve(n):
    primes = range(3, n + 1, 2) # primes above 2 must be odd so start at three and increase by 2
    for base in xrange(len(primes)):
        if primes[base] is None:
            continue
        if primes[base] > sqrt(n): # stop at sqrt of n
            break

        for i in xrange(base + (base + 1) * primes[base], len(primes), primes[base]):
            primes[i] = None
    primes.insert(0,2)
    return filter(None, primes)
    
arr=sieve(2*n)
count=0
if n<1:
	print 0
else:
	for item in arr:
		if item<=n:
			count=count+(item+1)
		else:
			count=count+(2*n-item+1)
			
	print count%mod