시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB104612953.704%

문제

양의 정수의 무한한 수열 $a_1, a_2, a_3, \cdots $이 다음 조건을 만족한다. $c$는 고정된 양의 정수이고 $c \geq 2$이다.

임의의 양의 정수 $n$에 대하여,

  • $a_n$이 $c$의 배수인 경우, $a_{n+1} = \frac{a_n}{c}$ 이다.
  • $a_n$이 $c$의 배수가 아닌 경우, $a_{n+1} = c^{a_n}$ 이다.

양의 정수 $m$에 대하여, $a_m + a_{m+1} = c+1$ 이 성립하도록 하는 모든 양의 정수 $a_1$의 합을 $S(m)$이라고 하자. 양의 정수 $M$이 주어졌을 때, $S(1), S(2), \cdots, S(M)$의 값을 각각 구하여라. 단, 값이 매우 커질 수 있으므로 $1\ 000\ 000\ 007$로 나눈 나머지를 출력한다.

입력

첫째 줄에 두 정수 $c, M$이 공백을 사이에 두고 주어진다.

출력

$M$개의 줄에 걸쳐 정답을 출력한다. $i(1 \leq i \leq M)$번째 줄에는 $S(i)$를 $1\ 000\ 000 \ 007$로 나눈 나머지를 하나의 음이 아닌 정수로 출력해야 한다. $1\ 000\ 000\ 007$은 소수이다.

제한

  • $2 \leq c \leq 10^9$
  • $1 \leq M \leq 100\ 000$
  • 주어지는 모든 수는 정수이다.

예제 입력 1

2 6

예제 출력 1

3
7
15
34
72
153

$c=2, M=6$ 이다.

$a_1 + a_2 = 3$일 필요충분조건은 $a_1 \in \left\{1, 2 \right\}$ 이므로, $S(1) = 1 + 2 = 3$이다.

$a_2 + a_3 = 3$일 필요충분조건은 $a_1 \in \left\{1, 2, 4 \right\}$ 이므로, $S(2) = 1 + 2 + 4 = 7$이다.

$a_6 + a_7 = 3$일 필요충분조건은 $a_1 \in \left\{1, 2, 3, 4, 5, 6, 8, 12, 16, 32, 64 \right\}$ 이므로, $S(6) = 1 + 2 + 3 + 4 + 5 + 6 + 8 + 12 + 16 + 32 + 64 = 153$이다.

예제 입력 2

142857 2

예제 출력 2

142858
408265167

$c = 142\ 857, M =2$ 이다.

$a_2 + a_3= 142\ 858$일 필요충분조건은 $a_1 \in \left\{1, 142\ 857, 20\ 408\ 122\ 449 \right\}$이므로, $S(2) = 1 + 142\ 857 + 20\ 408\ 122\ 449= 20\ 408\ 265\ 307$이다. 두 번째 줄에는 $20\ 408\ 265\ 307$을 $1\ 000\ 000\ 007$로 나눈 나머지인 $408\ 265\ 167$을 출력해야 한다.

출처

School > DGUPC > 제 2회 DGUPC I번