H. Kyooma Loves Tree
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kyooma 给了你一颗深度为 $$$n$$$ 的满 $$$k$$$ 叉树，其中每条边都有 $$$p$$$ 的概率消失，Kyooma 想知道最后留下的森林中树的个数的期望是多少？

对于只有一个点存在的树，我们认为它的深度为 $$$1$$$ 。

满 $$$k$$$ 叉树：除了叶节点外，每个节点都有恰好$$$k$$$个儿子，且所有叶节点深度相同。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10^5})$$$ ，代表测试组数。

随后 $$$T$$$ 行每行包含三个整数 $$$n,k,p$$$ $$$(1\le{n,k}\le{10^{18}},0\le{p} \lt {998244353})$$$，分别代表满 $$$k$$$ 叉树的深度，树上每个节点的儿子的个数和边消失的概率对 $$$998244353$$$ 取模的结果。

Output

对于每个测试输出一行，代表答案对 $$$998244353$$$ 取模后的结果。

Example
Input
2
2 2 499122177
114514 1919810 0
Output
2
1