← 返回题目列表

Codeforces · 2060/F

F. 乘法数组

中文机器翻译题面 查看原题

给你整数 $$$k$$$ 和 $$$n$$$。对于从 $$$1$$$ 到 $$$k$$$ 的每个整数 $$$x$$$,计算整数数组 $$$a$$$ 的数量,以满足以下所有条件:

- $$$1 \leq |a| \leq n$$$ 其中$$$|a|$$$ 表示$$$a$$$ 的长度。
- $$$1 \leq a_i \leq k$$$ 对于所有 $$$1 \leq i \leq |a|$$$。
- $$$a_1 \times a_2 \times \dots \times a_{|a|}=x$$$ (即所有元素的乘积为 $$$x$$$)。

请注意,如果两个数组 $$$b$$$ 和 $$$c$$$ 的长度不同,或者存在索引 $$$1 \leq i \leq |b|$$$ 使得 $$$b_i\neq c_i$$$ 是不同的。

输出对 $$$998\,244\,353$$$ 取模的答案。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t\leq 10^3$$$) — 独立测试用例的数量。

每个测试用例的唯一行包含两个整数 $$$k$$$ 和 $$$n$$$ ($$$1 \leq k \leq 10^5, 1\leq n \leq 9\cdot 10^8$$$)。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,在新行中输出 $$$k$$$ 以空格分隔的整数:$$$x=1,2,\ldots,k$$$ 的数组数量,模 $$$998\,244\,353$$$。

示例

输入 #1

3
2 2
4 3
10 6969420

输出 #1

2 3
3 6 6 10
6969420 124188773 124188773 729965558 124188773 337497990 124188773 50981194 729965558 337497990

注意

在第一个测试用例中,有 $$$2$$$ 数组 $$$a$$$ ,其中 $$$|a|\leq 2$$$ 且元素的乘积等于 $$$1$$$:

- $$$[1]$$$
- $$$[1,1]$$$

有 $$$3$$$ 数组 $$$a$$$,其中 $$$|a|\leq 2$$$ 且元素的乘积等于 $$$2$$$:

- $$$[2]$$$
- $$$[1,2]$$$
- $$$[2,1]$$$