← 返回题目列表

Codeforces · 1359/E

E. 模块化稳定性

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

我们将 $$$x \bmod y$$$ 定义为 $$$x$$$ 除以 $$$y$$$ 的余数(C++ 或 Java 中的 $$$\%$$$ 运算符,Pascal 中的 mod 运算符)。

如果对于从 $$$1$$$ 到 $$$k$$$ 的整数的每个排列 $$$p$$$,并且对于每个非负整数 $$$x$$$,满足以下条件,我们称正整数数组 $$$[a_1, a_2, \dots, a_k]$$$ 稳定:

$$$ (((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k} $$$

也就是说,对于每个非负整数 $$$x$$$,如果我们对数组 $$$a$$$ 的元素重新排序,$$$(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k$$$ 的值不会改变。

对于两个给定的整数 $$$n$$$ 和 $$$k$$$,计算稳定数组 $$$[a_1, a_2, \dots, a_k]$$$ 的数量,使得 $$$1 \le a_1 < a_2 < \dots < a_k \le n$$$。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$)。

输出

打印一个整数 — 稳定数组 $$$[a_1, a_2, \dots, a_k]$$$ 的数量,使得 $$$1 \le a_1 < a_2 < \dots < a_k \le n$$$。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。

示例

输入 #1

7 3

输出 #1

16

输入 #2

3 7

输出 #2

0

输入 #3

1337 42

输出 #3

95147305

输入#4

1 1

输出#4

1

输入 #5

500000 1

输出 #5

500000