9054: Expectation (Hard Version)

Note: The only difference between the easy and hard versions is the range of n and m . Please refer to the time limit set on the online judge!!! 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 ≤ m ≤ 106 , 1 ≤ n, 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 Pm ≤ 107 .

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

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 .