Ocean Deep! Make it shallow!

4

52 votes
Medium
Problem
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

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Prospective Cells Are :

(0,2) , (1,1) , (1,2) , (2,0) , (2,1)

Editor Image

?