9053: Expectation (Easy Version)

内存限制:512 MB 时间限制:4 S
题面:传统 评测方式:文本比较 上传者:
提交:6 通过:0

题目描述

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