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:
MOD = 1000000007
N = 2000001
prime = [0]*N
prime[0] = 1
prime[1] = 1
def sieve():
    i = 2
    while i*i <= N:
        j = 2*i
        if prime[i] != 1: 
            while j < N:
                prime[j] = 1
                j += i
        i += 1
def roy_and_rangoli():
    G = input()
    sieve()
    res = 0
    for i in xrange(G):
        if prime[i] == 0:
            res = res + i + 1
            res %= MOD
    #print res
    for i in xrange(G,2*G-1):
        if prime[i] == 0:
            t = (i+1) - 2*(i-(G-1))
            #t %= MOD
            res += t
            res %= MOD
    print res
roy_and_rangoli()