409506: GYM103604 A CoinFlip

Ely found a magic number $$$K$$$, a magic basket with exactly one strawberry in it, and a magic coin. Everything seems to be magical.

Ely notices that when tossing the coin it falls heads up with probability $$$P$$$. Also, each time the coin falls heads up the number of strawberries in the basket get $$$K$$$ times bigger (i.e. if in the basket were $$$x$$$ strawberries, after the toss there will be $$$x \times K$$$). Ely decides to play the following game: she will toss the coin $$$N$$$ times; if it falls heads up she will just notice as the strawberries multiply $$$K$$$ times; if the coin falls tails up she will eat all the strawberries in the basket. After eating all the strawberries in the basket something magical happens: precisely a single new strawberry spawns inside of the basket.

Ely is now curious what is the expected number of strawberries she would eat after $$$N$$$ coin tosses. Help her find the answer.

The first line of the input will contain an integer $$$T$$$, the number of test cases ($$$1 \leq T \leq 10^5$$$).

Each of the next $$$T$$$ lines will contain three integers $$$N_i$$$ ($$$1 \leq N_i \leq 10^{18}$$$), $$$K_i$$$ ($$$0 \leq K_i < 998244353$$$), $$$P_i$$$ ($$$0 \leq P_i < 998244353$$$) the number of coin flips, the increasing factor for the strawberries and the probability that the coin lands head up, for the $$$i$$$th test case. The probability is a fraction $$$\frac{a}{b}$$$ given as $$$a \times b^{-1}$$$ (modulo 998244353), where $$$b^{-1}$$$ is the modular inverse of $$$b$$$ modulo 998244353.

The output file should contain $$$T$$$ lines, each with a single integer $$$A_i$$$, the answer for $$$i$$$th test case modulo 998244353.

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

499122177
748683267
748683281
565383148