Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

题目描述

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