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.
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 × 1m +
3/8 × (1m + 2m) + 1/8 × (1m + 2m + 3m).
So your first three answers are 9/4
, 4,
33/4
.