You are given four integers a, d, K, and N. Consider N numbers, \(b_1, b_2, ...\ , b_N\) where \(b_i = a + (i - 1) \times d\). Your task is to evaluate the following sum:
- \(\sum\limits_{v_1 \geq 0, v_2 \geq 0, .., v_N \geq 0\)\(v_1 + v_2 + .. + v_N = k} \left(\prod\limits_{i=1}^{N} b_i^{v_i}\right)\)for each k = 0, 1, 2,... , K
Since the sum can be very large, you are required to print it modulo \(998244353\).
Note: The sum is over all ordered tuples \((v_1, v_2, ...\ , v_N)\) satisfying \(\sum\limits_{i=1}^{N} v_i = k\).
Input format
- The first line contains a single integer T denoting the number of test cases.
- The first line of each test case contains four space-separated integers a, d, K, and N.
Output format
For each test case (in a separate line), print K + 1 space-separated integers in a new line denoting the sum for each k = 0, 1, 2, .. ,K. Print the output modulo \(998244353\).
Constraints
2 1 3 3 3 2 1 2 4
1 12 105 820 1 14 125
In the first test case we have, $$a = 1, d = 3, K = 3, N = 3$$. Therefore, $$b_1 = 1, b_2 = 4, b_3 = 7$$. We need to sum over tuples of the form $$(v_1, v_2, v_3)$$ satisfying $$\sum\limits_{i=1}^{N} v_i = k$$.
- For $$k = 0$$, we have only 1 tuple $$(0, 0, 0)$$, and the sum is $$1$$.
- For $$k = 1$$, we have 3 possible tuples : $$(1, 0, 0), (0, 1, 0), (0, 0, 1)$$. The sum comes out to be $$b_1 + b_2 + b_3 = 1 + 4 + 7 = 12$$.
- For $$k = 2$$, we have 6 possible tuples : $$(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0), (1, 0, 1), (0, 1, 1)$$. The sum comes out to be $$b_1^2 + b_2^2 + b_3^2 + b_1 * b_2 + b_2*b_3 + b_1 * b_3 = 1 + 16 + 49 + 4 + 28 + 7 = 105$$.
- For $$k = 3$$, we have 10 possible tuples : $$(3, 0, 0), (0, 3, 0), (0, 0, 3), (1, 2, 0), (2, 1, 0), (0, 1, 2), $$$$(0, 2, 1), (1, 0, 2), (2, 0, 1), (1, 1, 1)$$. The sum comes out to be $$b_1^3 + b_2^3 + b_3^3 + b_1 * b_2^2 + b_1^2 * b_2 + b_2 * b_3^2 + b_2 ^2 * b_3 + b_1 * b_3^2 + b_1^2 * b_3 + b_1 * b_2 * b_3 = 820$$.
- Note that we output answers in a single line.
In the second test case we have, $$a = 2, d = 1, K = 2, N = 4$$. Therefore, $$b_1 = 2, b_2 = 3, b_3 = 4, b_4 = 5$$. We need to sum over tuples of the form $$(v_1, v_2, v_3, v_4)$$ satisfying $$\sum\limits_{i=1}^{N} v_i = k$$.
- For $$k = 0$$, we have only 1 tuple $$(0, 0, 0)$$, and the sum is $$1$$.
- For $$k = 1$$, we have 4 possible tuples : $$(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)$$. The sum comes out to be $$b_1 + b_2 + b_3 + b_4 = 2 + 3 + 4 + 5= 14$$.
- For $$k = 2$$, we have 8 possible tuples. The sum comes out to be $$b_1^2 + b_2^2 + b_3^2 + b_4^2 + b_1 * b_2 + b_2*b_3 + b_1 * b_3 + b_1*b_4 + b_2*b_4 + b_3*b_4 = 125$$.
- Note that we output answers in a single line.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor