만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

선의 개수 세기

시간 제한2초메모리 제한512 MB

요약
n이 주어지면 1 ≤ x ≤ y ≤ n을 만족하는 격자점 중 두 점 이상을 지나는 서로 다른 직선의 개수를 10^9+7로 나눈 나머지로 구합니다.
난이도

어려움10점 중 9점

유형
정수론, 기하, 수학
정답자
아직 제출이 없습니다

문제

Bobo에게는 점들의 집합 PP가 있다. PP의 원소는 n(n+1)2\frac{n(n + 1)}{2}개이며, PP는 {(x,y):1≤x≤y≤n, x,y∈Z}\{ (x, y) : 1 \leq x \leq y \leq n, \ x, y \in \mathbb{Z} \}이다. Bobo는 PP에 있는 점 두 개 이상을 지나는 서로 다른 직선의 개수를 알고 싶어 한다. 이 개수를 (109+7)(10^9+7)로 나눈 나머지를 구한다.

입력

입력에는 테스트 케이스가 0개 이상 들어 있으며, 파일 끝(EOF)에서 입력이 끝난다. 각 테스트 케이스는 정수 nn (2≤n≤2⋅1092 \leq n \leq 2 \cdot 10^9)이 한 줄에 주어진다.

테스트 케이스의 개수는 10510^5을 넘지 않으며, 모든 nn의 합은 2⋅1092 \cdot 10^9을 넘지 않는다고 보장된다.

출력

각 테스트 케이스마다 서로 다른 직선의 개수를 (109+7)(10^9+7)로 나눈 나머지를 정수 하나로 출력한다.

예제1

  1. 예제 1

    입력
    2
    3
    5
    
    예상 출력
    3
    9
    51