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:
__author__ = 'Admin'

limit = int(raw_input())
if limit == 1:
    print 0
else:
    limit = limit - 1
    list_of_primes = []
    for i in range(0 , limit * 2 + 1):
        list_of_primes.append(0)
    list_of_primes[0] = 1
    list_of_primes[1] = 1
    i=2
    while(i * i <= limit*2):
        if list_of_primes[i] == 0:
            k = 2
            j = i * k
            while(j <= limit*2):
                list_of_primes[j] = 1
                k = k + 1
                j = i * k
        i = i + 1

    # print list_of_primes
    cnt = 0
    for i in range(0 , limit+1):
        if list_of_primes[i] == 0:
            cnt = cnt + (i+1)
            cnt = cnt % 1000000007
    j = limit
    i = limit+1
    while(i < limit*2 + 1):
        if list_of_primes[i] == 0:
            cnt = cnt + (j)
            cnt = cnt % 1000000007
        j = j - 1
        i = i + 1

    print cnt