1417: 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 $\frac ab$ to win. |
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$
输入
The first line of the input contains an integer $T\ (1\le T \le 20)$, indicating the number of the test cases
It's guaranteed that $\sum n\le 10^7$.
| The next $T$ lines, each line has four integers $n, m, a, b\ (1\le n\le 10^6, 1 \le 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 $\frac ab$. |
输出
$T$ lines, each line has one interger, indicating the answer.
样例输入 Copy
4
3 1 1 2
3 2 1 2
3 3 1 2
114514 1000000 123456789 987654321
样例输出 Copy
748683267
4
748683273
733239168
提示
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$.
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$.