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 main():
	n=int(raw_input())
	primear=[True for i in range(2*n)]
	primear[0]=primear[1]=False;
	for i in range(2*(n-1)):
		if(primear[i]):
			j=i+i;
			while(j<2*n):
				primear[j]=False;
				j+=i;
	ans=0
	if n==2:
		print "1"
		return
	for i in range(2*(n-1)):
		if(primear[i]):
			if(i<n):
				ans+=(i+1);
				ans%=1000000007
			else:
				opp=i-(n-1)
				ans+=(n-1-(opp))
				ans+=1
				ans%=1000000007

	print ans
main()