题目描述
在一个游戏里， 赵悦岑扮演一只鹅。鹅的任务是把鸭子消灭。一共有 $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 192608173
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$ |