Problem Description

Yili found a magic number $K$, a magic basket full of strawberries, and a magic coin.

Yili noticed that when flipping the coin, it has a probability of $P$ to land heads up. Then she flips the coin $n$ times. If the coin lands heads up, the strawberries in the basket become $K$ times the original amount. Otherwise, she will eat all the strawberries in the basket. After she finishes eating, the basket will magically produce one new strawberry.

Yili is now curious about the expected number of strawberries she will eat after flipping the coin $n$ times. Please tell her the answer modulo $998244353$.

Input Format

The first line contains an integer $T$, indicating the number of test cases.

The next $T$ lines each contain three integers $n, K, P$.

Output Format

Output $T$ lines. Each line contains a positive integer representing the answer.

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

499122177
748683267
748683281
565383148

Hint

Constraints

For $100\%$ of the testdata, it holds that $1 \leq T \leq 10^5$, $1 \leq n \leq 10^{18}$, and $0 \leq K, P < 998244353$.

Notes

Translated from AGM 2022 Qualification Round A CoinFlip。

Translated by ChatGPT 5