| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 146 | 55 | 42 | 32.558% |
인형 뽑기 기계를 실행시킬 때마다 랜덤하게 $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}$을 출력한다.
1 500000004 2 5
500000004 250000003 875000008 62500003 968750010
예제 입력은 $p = \frac{1}{2}$인 경우이고, 출력은 각각 $\frac{1}{2},ドル $\frac{5}{4},ドル $\frac{15}{8},ドル $\frac{41}{16},ドル $\frac{103}{32}$과 동일한 의미이다.