Copium là một vua trò chơi, với bất kể trò chơi nào trên đời thì anh ta luôn đứng ở vị trí thứ ~1~, chỉ cho đến khi illya xuất hiện. Ban đầu biết rằng sẽ rất khó để đánh bại anh trong các trò chơi có sẵn, illya quyết định tự nghĩ ra một trò chơi như sau: Cho một dãy các số nguyên dương từ ~1~ đến ~n~, illya sẽ chọn ra một cặp số là ~(a_1, a_2)~, Copium sẽ phải chọn ra một cặp số là ~(b_1, b_2)~. Vì là một người rất kĩ tính, để nắm chắc phần thắng thì illya cần đếm số trường hợp thỏa mãn :

• ~a_1, a_2, b_1, b_2~ là ~4~ số phân biệt nhau.
• ~a_1 \times a_2 > b_1 \times b_2~ .

Hãy giúp illya giành phần thắng trước Copium nhé!

Input

• Gồm một số nguyên duy nhất là ~n~ ~(4 \leq n \leq 10^7)~

Output

• Gòm một số nguyên duy nhất là số trường hợp thỏa mãn yêu cầu đề bài. Vì số trường hợp có thể rất nhiều nên hãy in ra đáp án với phần dư khi chia cho ~10^9 + 7~

Subtask

• Có ~30\%~ số test thỏa mãn ~1 \leq n \leq 2000~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

4

Sample Output

3

Note

Ta có dãy ~{1, 2, 3, 4}~, sẽ có các trường hợp thỏa mãn sau đây:

• illya có cặp số ~{3, 4}~ và Copium có cặp số ~{1, 2}~, thỏa mãn ~3 \times 4 > 1 \times 2~. Vì vậy illya thắng.
• illya có cặp số ~{2, 4}~ và Copium có cặp số ~{1, 3}~, thỏa mãn ~2 \times 4 > 1 \times 3~. Vì vậy illya thắng.
• illya có cặp số ~{2, 3}~ và Copium có cặp số ~{1, 4}~, thỏa mãn ~2 \times 3 > 1 \times 4~. Vì vậy illya thắng.