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:
def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False

    return True
def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]
a=input()
c=0
d=0
b=primes_sieve1(2*(a-1))
for j in range(0,len(b)):
	if((a-1)>=b[j]):
		c+=b[j]+1
	elif(a==b[j]):
		c+=b[j]-1
	else:
		d+=(a-1)-(b[j]-(a-1))+1
print((c+d)%1000000007)