거듭제곱 수열의 합

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

요약

c와 M이 주어질 때, 각 m에 대해 a_m + a_{m+1} = c+1을 만족하는 a_1의 합 S(m)을 10^9+7로 나눈 나머지로 M개 구합니다.

난이도: 어려움10점 중 9점
유형: 정수론, 수학, 재귀
정답자: 아직 제출이 없습니다

문제

양의 정수로 이루어진 무한 수열 $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$
주어지는 모든 수는 정수이다.

예제2

예제 1
입력
```
2 6
```
예상 출력
```
3
7
15
34
72
153
```
예제 2
입력
```
142857 2
```
예상 출력
```
142858
408265167
```