Ocean deep
I'm so afraid to show my feelings,
I have sailed a million ceilings
In my solitary room
Ocean deep
Lines are from a famous song by Cliff Richard. Today we are dealing with a similar person. His name is Polymnia and the important thing is he is dead. Nobita and Doraemon are detectives to this case. Polymnia has a solitary room in form of a NxN grid in which he has hidden his diary under one of the cells.
Nobita and Doraemon have come to know that the diary must be hidden only under some prospective cells. Cell located at ith row and jth column is prospective iff i+j is prime. Consider zero-based indexing.
So they want to know how many prospective cells are there in a grid of NxN.
Input
One integer N denoting side of the square grid.
Output
Print a single integer, number of prospective cells. As the answer can be very large, output it modulo 10^9+7
Constraints
1<= N <=1000000
Author: Karan Thakkar
Tester: Akshat Dua
Prospective Cells Are :
(0,2) , (1,1) , (1,2) , (2,0) , (2,1)