题目描述

伊利找到了一个魔法数字 $K$，一个装满草莓的魔法篮子，还有一个魔法硬币。

伊利注意到，当抛硬币时，它有 $P$ 的概率概率朝上。随后她抛了 $n$ 次硬币，如果硬币朝上篮子里的草莓会变成原来的 $K$ 倍。否则，她会吃掉篮子里的所有草莓，吃完后篮子会神奇地变出一颗新的草莓。

伊利现在很好奇她在抛 $n$ 次硬币后期望会吃多少草莓。请你告诉她答案在 $\bmod\ 998244353$ 意义下的答案。

输入格式

第一行一个数 $T$，表示数据组数。

接下来 $T$ 行，每一行三个数表示 $n,K,P$。

输出格式

$T$ 行，每行一个正整数表示答案。

4
1 2 499122177
3 2 499122177
10 2 499122177
1000000000000000000 100 16235235

499122177
748683267
748683281
565383148

提示

数据规模与约定

对于 $100\%$ 的数据，满足 $1\leq T\leq 10^5$，$1\leq n \leq 10^{18}$，$0\leq K,P<998244353$。

说明

翻译自 AGM 2022 Qualification Round A CoinFlip。