题目描述
在一个游戏里, 赵悦岑扮演一只鹅。鹅的任务是把鸭子消灭。一共有 $n+1$ 只鹅,即赵悦岑有 $n$ 个队友。
不幸的是,这 $n$ 个队友中有一个是鸭子假扮的,称作“模仿鸭”。模仿鸭和鹅外形上完全相同, 赵悦岑无法分辨。 赵悦岑的任务是把这只模仿鸭消灭。 赵悦岑一次可以同时向 $k$ 只鹅发动攻击。因为鹅身手敏捷,所以鹅会一定闪避掉 的攻击。而模仿鸭有 $p$ 的概率会被击中,从而被消灭;$1-p$ 的概率会闪避这次攻击。注意如果一只鸟闪避了攻击, 赵悦岑无法得知攻击对象是否是模仿鸭。
假设赵悦岑足够聪明(当然这是不可能的),求赵悦岑消灭模仿鸭需要的攻击次数的期望,答案对 $998244353$ 取模。
因为赵悦岑沉迷这个游戏,所以你要对 $T$ 组询问分别回答答案。
输入格式
第一行一个数 $T$ 表示数据组数。 下面 $T$ 行,每行三个数 $n,k,p$,含义如上文所示。给出的 $p$ 是在模意义下的。
输出格式
对于每组数据输出一行一个数,表示这组数据的答案。
样例
3
1 1 332748118
3 2 499122177
1919810 114514 19260817
3
110916042
182546539
数据范围
$1\le k \le n \le 10^{12},1\le p < 998244353,1\le T \le 1000$
子任务 | $n$ | $k$ | $p$ | $T$ | 分值 |
---|---|---|---|---|---|
1 | $\le 1000$ | $\le 10$ | $15$ | ||
2 | $\le 2\times 10^5$ | $n\bmod k=0$ | $\le 10$ | $10$ | |
3 | $\le 2\times 10^5$ | $\le 10$ | $20$ | ||
4 | $n\bmod k=0$ | $10$ | |||
5 | $=1$ | $5$ | |||
6 | $=\frac{1}{2}$ | $10$ | |||
7 | $30$ |