Yukikaze is studying the theory of random graphs.
In the probability version of the Erdős-Rényi model, a random graph is constructed by connecting nodes randomly. That is, the random graph G(n,p) is an undirected graph with n vertices, and each edge from the 2n(n−1) possible edges is included in the graph with probability pp independently from every other edge.
Now she wonders about the expected number of connected components in G(n,p), modulo a large prime 998244353
The first line of the input contains a single integer T (1≤T≤100), denoting the number of test cases.
The first line of each test case contains three integers q,a,b(1≤q≤105, 1≤a≤b<998244353), denoting the number of queires and the probability p=a/b.
The second line of each test case contains q integers n1,n2,…,nq (1≤ni<5×105 for each 1≤i≤q) seperated by spaces, denoting that Yukikaze wants to know the expected number of connected components in G(n_i,p)G(ni,p).
Let N be the sum of the maximum ni of each test case, and Q be the sum of q of all test cases. It's guaranteed that N≤5×105 and Q≤105.
For each test case, output a single line containing the answers to the queries separated by spaces. You should output the answers modulo 998244353. That is, if the answer is QP, you should output P⋅Q−1mod998244353, where Q−1 denotes the multiplicative inverse of Qmodulo 998244353. We can prove that the answer can always be expressed in this form.
Don't output any extra spaces at the end of each line.
3
1 14 51
4
1 91 98
10
2 114 514
1919 810798850218
132789114
904977379 493892762