숫자 로얄

자연수 나라에서는 축제를 맞이하여 숫자 로얄 경기를 한다. 경기에는 1부터 N(N은 300,000이하의 자연수)까지의 자연수가 출전한다.

숫자 로얄은 개인전으로, 참가한 수들이 서로의 강함을 겨루고 1등을 가린다. 각 숫자들의 강함은 다음 규칙을 통해 결정한다:

1. 소수(素數)는 소수가 아닌 수를 무조건 이긴다.
2. 큰 수는 작은 수를 이긴다.

예시로, 2와 6이 겨룬다면, 2는 소수이기 때문에 6을 이긴다. 2와 3이 겨룬다면, 둘 다 소수이므로 3이 2를 이긴다.

출전한 자연수들은 서로 만들 수 있는 모든 조합으로 경기를 진행한다. 예를 들어, 1, 2, 3이 출전했다면, (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3), 총 7번의 경기가 진행된다. 경기를 치루고 서로의 강함을 증명하면 1등부터 꼴지까지 무조건 정해진다. 경기가 끝나면 관객들은 각 경기에 참여 했던 숫자 중(일등 숫자 - 꼴지 숫자)만큼 행복도를 얻는다. 행복도는 음수가 될 수 있다.

입력으로 자연수 N이 주어질 때, 모든 경기 진행 후, 관객들이 얻게되는 행복도의 총 합을 구하시오. 만약 행복도의 총 합이 1,000,000,007보다 크다면, 1,000,000,007으로 나눈 나머지를 구하시오.

*영감을 받은 문제: https://www.acmicpc.net/problem/15824