Fully Generate

시간 제한0.5초메모리 제한1024 MB

요약

n이 최대 10^12일 때 골롬 자기서술 수열의 첫 n개 항의 곱을 1,000,000,007로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론
정답자: 아직 제출이 없습니다

문제

양의 정수 만으로 이루어진 단조 증가 수열 $G$ 가 있다. 이 수열에서 $G\_i$ 는 $i$ 가 $1$ 이상의 정수일 때 정의되며, $G$ 에서 $i$ 가 등장하는 횟수를 나타낸다. 정확히 말하면, $G$ 는 $i$ 가 $G\_i$ 번 나타나는 수열이어야 한다. $G\_1 = 1$ 이며, 이 때 $G$ 는 유일하게 결정된다. $G\_1$ 에서 $G\_{12}$ 까지를 순서대로 적어보면 다음과 같다.

$1$ , $2$ , $2$ , $3$ , $3$ , $4$ , $4$ , $4$ , $5$ , $5$ , $5$ , $6$ , $\cdots$

$1$ 이 $1$ 번, $2$ 가 $2$ 번, $3$ 이 $2$ 번, $4$ 가 $3$ 번, $5$ 가 $3$ 번 등장하는 것을 볼 수 있다.

$n$ 이 주어질 때, $G\_1$ 에서 $G\_n$ 까지의 곱을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 하나의 정수 $n$ ( $1 ≤ n ≤ 10^{12}$ )이 주어진다.

출력

$G\_1$ 에서 $G\_n$ 까지의 곱을 출력한다. 이 수가 매우 클 수 있으므로, $1\\,000\\,000\\,007$ 로 나눈 나머지를 출력하도록 한다.

예제11

예제 1
입력
```
1
```
예상 출력
```
1
```
예제 2
입력
```
2
```
예상 출력
```
2
```
예제 3
입력
```
3
```
예상 출력
```
4
```
예제 4
입력
```
4
```
예상 출력
```
12
```
예제 5
입력
```
5
```
예상 출력
```
36
```
예제 6
입력
```
6
```
예상 출력
```
144
```
예제 7
입력
```
7
```
예상 출력
```
576
```
예제 8
입력
```
8
```
예상 출력
```
2304
```
예제 9
입력
```
9
```
예상 출력
```
11520
```
예제 10
입력
```
10
```
예상 출력
```
57600
```
예제 11
입력
```
100
```
예상 출력
```
711574837
```