问题 G: Expectation (Easy Version)

Note: The only difference between the easy and hard versions is the range of n and m . You are to play a game for n times. Each time you have the probability a b to win. If you win, you will get k m score, where k is the total times you win at that time, otherwise you won’t get any score. Your final score is the sum of the score you get each time. For instance, if n = 5, m = 10, and you win twice in total, your final score is 1 10 + 210 = 1025. Now you wonder the expectation of your final score modulo 998244353.

The first line of the input contains an integer T (1 ≤ T ≤ 20), indicating the number of the test cases. The next T lines, each line has four integers n, m, a, b (1 ≤ n ≤ 106 , 1 ≤ m, a, b < 998244353), indicating the number of games you play, the power of k is m, and the probatility to win a game is a/b . It’s guaranteed that Pn ≤ 107 .

T lines, each line has one interger, indicating the answer.

4
3 1 1 2
3 2 1 2
3 3 1 2
114514 1000000 123456789 987654321

748683267
4
748683273
733239168

In first three test cases, you have the probability of 3/8 to win once, 3/8 to win twice, 1/8 to win three times. The expectation of your final score is 3/8 × 1^m + 3/8 × (1^m + 2^m) + 1/8 × (1^m + 2^m + 3^m). So your first three answers are 9/4 , 4, 33/4 .