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:
3
5
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor