#P13541. [OOI 2022] Good arrays

[OOI 2022] Good arrays

Description

最近,Vasya 学会了整数除法。受到这项神奇知识的启发,他决定进一步了解满足某些整除性质的正整数数组。更具体地说,Vasya 称一个数组 a={a1,a2,,an}a = \{a_1, a_2, \ldots, a_n\}好数组,当且仅当对于每个 ii11n1n-1aia_i 能被 ai+1a_{i+1} 整除。

请你帮助他计算长度为 nn,且所有元素均为不超过 cc 的正整数的好数组的数量。

Input Format

输入仅一行,包含两个整数 nncc1n,c5×1071 \le n, c \le 5 \times 10^7),分别表示数组的长度和元素的最大允许值。

Output Format

输出一个整数,表示所有长度为 nn、元素不超过 cc 的好数组的数量。由于答案可能非常大,请输出对 998244353998\,244\,353 取模后的结果。

3 3
7
2 6
14

Hint

本题的测试数据分为 7 组。只有在通过某一组的所有测试点以及所有必需的前置组后,才能获得该组的分数。

离线评测表示该组的评测结果将在比赛结束后公布。

组别 分值 附加限制 nn cc 子任务依赖 备注
0 - - 样例测试点
1 15 n10n \le 10 c10c \le 10 0
2 14 n1000n \le 1000 c1000c \le 1000 0, 1
3 12 n5000n \le 5000 c5000c \le 5000 0-2
4 16 n100000n \le 100\,000 c100000c \le 100\,000 0-3
5 14 n106n \le 10^6 c106c \le 10^6 0-4
6 15 n107n \le 10^7 c107c \le 10^7 0-5
7 14 - 0-6 离线评测