Problem Description

**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 $\frac ab$ 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} + 2^{10}=1025$.

Now you wonder the expectation of your final score modulo $998244353$.

Input

The first line of the input contains an integer $T\ (1\le T\le 20)$, indicating the number of the test cases.

The next $T$ lines, each line has four integers $n, m, a, b\ (1\le m\le 10^6, 1 \le 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 $\frac ab$.

It's guaranteed that $\sum m\le 10^7$.

Output

$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

Hint

In first three test cases, you have the probability of $\frac 38$ to win once, $\frac 38$ to win twice, $\frac 18$ to win three times.

The expectation of your final score is $\frac 38\times 1^m+\frac 38\times(1^m+2^m)+\frac 18\times(1^m+2^m+3^m)$.

So your first three answers are $\frac 94,4,\frac{33}4$.