Cho một lưới có kích thước \(n × n\), các dòng được đánh số từ \(0\) đến \(n-1\), các cột được đánh số từ \(0\) đến \(n-1\). Tí muốn tô màu đỏ cho một số ô trong lưới.

Ô nằm ở hàng thứ \(i\) và cột thứ \(j\) sẽ được tô màu nếu tổng \(i+j\) là số nguyên tố.

Yêu cầu: Tí muốn biết cậu cần tô bao nhiêu ô trong lưới với kích thước n×n

Input

• Gồm một dòng chứa số nguyên \(n (1 ≤ n ≤ 10^6 )\)

Output

• In ra một số nguyên, là số ô mà Tí sẽ phải tô màu. Do kết quả có thể rất lớn, hãy lấy kết quả theo modulo \(10^9+7\).

Sample Input

3

Sample Output

5

Ràng buộc:

• Subtask 1: \(n ≤ 1000\)
• Subtask 2: \(n ≤ 10^6 \)