15번

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