30963번 - 인형 뽑기

인형 뽑기 기계를 실행시킬 때마다 랜덤하게 $p = \frac{a}{b}$ 확률로 인형이 나온다. 단, 직전 $c - 1$번의 실행 중 인형이 하나도 나오지 않았다면 확률과 관계없이 확정적으로 인형이 나온다.

$p$, $c$, $n$이 주어지면, $n$ 이하의 모든 자연수 $k$에 대하여, 기계를 정확히 $k$번 실행시킨 시점에 얻는 인형 개수의 기댓값을 구하여라.

입력은 $T$개의 테스트 케이스로 이뤄지며, 첫 번째 줄에 정수 $T$가 주어진다. $(1 \le T \le 1\,000\,000)$

각 테스트 케이스는 한 줄로 이뤄져 있으며, 인형 뽑기 기계에서 인형이 나올 확률을 의미하는 정수 $p'$, 확정적으로 인형을 받기 위한 시행 횟수 $c$, 문제의 $n$이 공백으로 구분되어 주어진다. $(0 \le p' \le 10^9+6;$ $1 \le c, n \le 10^6)$ 이 때, $p' \equiv a \times b^{-1} \pmod{10^9 + 7}$을 만족하는 정수이다. $(b \not \equiv 0 \pmod{10^9+7})$

모든 테스트 케이스의 $n$의 합은 $10^6$ 이하이다.

각 테스트 케이스마다 $n$개의 줄에 걸쳐, $k$번째 줄에 기계를 정확히 $k$번 실행시킨 시점에 얻는 인형 개수의 기댓값을 $10^9+7$로 나눈 나머지를 출력한다. 정확히 말하면, 정답을 적당한 자연수 $x$, $y$가 있어 $\frac{x}{y}$로 표현 가능할 때 $x \times y^{-1} \pmod{10^9+7}$을 출력한다.