인형 뽑기

인형 뽑기 기계를 한 번 실행할 때마다 확률 $p = \frac{a}{b}$로 인형이 나온다. 단, 직전 $c - 1$번의 실행에서 인형이 하나도 나오지 않았다면, 확률과 관계없이 이번 실행에서는 반드시 인형이 나온다.

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

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

각 테스트 케이스는 한 줄로 이루어져 있으며, 공백으로 구분된 정수 $p'$, $c$, $n$이 주어진다. $p'$은 인형이 나올 확률을 나타낸다. $(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}$을 출력한다.