Việc học lập trình thuật toán thật sự rất cô đơn, Ali Vũ nhận thấy mình và các bạn bè trong lớp chuyên Tin cùng trang lứa cũng giống như các số nguyên tố. Mỗi người mỗi nơi, ít khi có dịp nào làm chung với nhau công việc gì. Các số nguyên tố cũng vậy, tách rời nhau và gần như không có số nào đứng cạnh nào trong dãy số tự nhiên. Để làm rõ hơn điều đó, Vũ bèn rủ bạn Ban cùng lớp chơi một trò chơi như sau: Vũ sẽ viết lên bảng các số nguyên dương từ 1 đến ~n~ theo thứ tự tùy ý, và Ban sẽ đếm xem có bao nhiêu cặp số nguyên tố đứng cạnh nhau trong dãy đó. Một điều thú vị là kết quả thu được cũng không tệ, tức là số cặp nguyên tố cạnh nhau cũng khá nhiều, dù Vũ đã thử viết lên nhiều thứ tự khác nhau. Vì thế, Vũ đổi lại luật lại tí xíu: Vũ sẽ viết các số lên bảng sao cho chẵn, lẻ xen kẽ nhau và nhờ Ban đếm lại. Quả thật, số cặp số nguyên tố đứng cạnh nhau đã giảm đi rõ rệt đúng như Vũ mong muốn.

Yêu cầu: hãy giúp Vũ tính xem khi xét tất cả các cách viết có thể có, mỗi cách là một hoán vị chẵn lẻ xen kẽ của các số ~1,2,...,n~ thì tổng số các cặp số nguyên tố đứng cạnh nhau là bao nhiêu?

Input

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^7.~

Output

Kết quả của bài toán, lấy modulo ~10^9+7.~

Sample input

4

Sample output

6

Giải thích

Các hoán vị có thể có với số cặp tương ứng là: ~(1, 2, 3, 4)~: ~1~ cặp, ~(3, 2, 1, 4)~: ~1~ cặp, ~(1, 4, 3, 2)~: ~1~ cặp, ~(3, 4, 1, 2)~: ~0~ cặp, ~(2, 1, 4, 3)~: ~0~ cặp, ~(2, 3, 4, 1)~: ~1~ cặp, ~(4, 1, 2, 3)~: ~1~ cặp, ~(4, 3, 2, 1)~: ~1~ cặp. Tổng cộng có ~6~ cặp thỏa mãn.

Ràng buộc

• Có ~20\%~ số test ứng với ~n \le 12.~
• Có ~50\%~ số test ứng với ~n \le 10^4~ và ~n~ chẵn.
• Có ~30\%~ số test ứng với ~n \le 10^7.~