P8229 [AGM 2022 Qualification Round] Coin Flip

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$.

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 $T$ lines. Each line contains a positive integer representing the answer.

#### 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](https://judge.agm-contest.com/public/problems/21/text)。 Translated by ChatGPT 5