对于数组 $$$[b_1, b_2, \ldots, b_m]$$$,其中 $$$0 \le b_i \le m$$$,将 $$$f(b)$$$ 定义为数组 $$$[c_1, c_2, \ldots, c_m]$$$,这样 $$$c_i$$$ 是出现的次数$$$i$$$ 在数组 $$$b$$$ 中。
定义 值 $$$g(b)$$$ 的数组 $$$[b_1, b_2, \ldots, b_m]$$$,其中 $$$0 \le b_i \le m$$$,如下所示:
- 最初,有一个空集$$$S$$$。创建一个数组 $$$d$$$,最初等于 $$$b$$$。
- 然后,执行以下操作$$$100^{100}$$$次:将$$$d$$$插入$$$S$$$,然后设置$$$d \gets f(d)$$$。
- $$$g(b)$$$ 是操作后$$$S$$$ 中不同数组的数量。
现在给你两个整数 $$$n$$$ 和 $$$k$$$,以及一个数组 $$$[r_1, r_2, \ldots, r_n]$$$。对于每个 $$$1\le p\le k$$$,计算数组 $$$[a_1, a_2, \ldots, a_n]$$$ 的数量,其中 $$$0 \le a_i \le r_i$$$ 使得 $$$g(a) = p$$$。由于这个数字可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le k \le 1000$$$)。
第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$)。
保证所有测试用例的$$$n^3$$$总和不超过$$$50^3$$$。
输出
对于每个测试用例,输出 $$$k$$$ 整数 - 数组 $$$[a_1, a_2, \ldots, a_n]$$$ 与 $$$0 \le a_i \le r_i$$$ 的数量,使得 $$$g(a) = 1, 2, \ldots, k$$$ 分别。
打印以 $$$998\,244\,353$$$ 为模的答案。
示例
输入复制
62 52 25 64 5 1 4 57 77 6 5 5 6 7 611 75 8 9 10 11 4 10 11 7 8 1112 712 12 12 12 12 12 12 12 12 12 12 125 100 0 0 0 1
输出复制
2 1 2 2 22 4 14 60 554 3952 6 35 627 63856 171611 4902352 10 83 10495 286935908 71004446 6302810802 11 132 48996 207819517 474452948 138283021 1 0 0 0 0 0 0 0 0
注意
在第一个测试用例中, $$$g([0, 0]) = g([1, 0]) = 1$$$, $$$g([0, 1]) = 2$$$, $$$g([2, 0]) = g([0, 2]) = 3$$$, $$$g([1, 1]) = g([2, 2]) = 4$$$ 和 $$$g([1, 2]) = g([2, 1]) = 5$$$。
在第二个测试用例中, $$$f([4, 5, 1, 4, 5]) = [1, 0, 0, 2, 2]$$$, $$$f([1, 0, 0, 2, 2]) = [1, 2, 0, 0, 0]$$$, $$$f([1, 2, 0, 0, 0]) = [1, 1, 0, 0, 0]$$$, $$$f([1, 1, 0, 0, 0]) = [2, 0, 0, 0, 0]$$$, $$$f([2, 0, 0, 0, 0]) = [0, 1, 0, 0, 0]$$$, $$$f([0, 1, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$, $$$f([1, 0, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$。所以,$$$g([4, 5, 1, 4, 5]) = 7$$$。