#P12632. 「OOI 2022 Day 1」好数组

「OOI 2022 Day 1」好数组

题目描述

瓦西娅最近刚刚学会了整数整除的概念。受到这一知识的极大启发,他开始研究数组中数字之间整除关系的性质。瓦西娅将一个包含 nn 个正整数的数组 a1,a2,a3,,ana_1, a_2, a_3, \ldots, a_n 定义为好数组,如果对于任意 ii(从 11n1n-1),数字 aia_i 都能整除数字 ai+1a_{i+1}。瓦西娅非常喜欢研究好数组,因此他想知道,元素个数为 nn 且所有数字不超过 cc 的好数组一共有多少个。

输入格式

唯一一行包含两个整数 nncc (1n,c5107)(1 \leq n, c \leq 5 \cdot 10^{7}),分别表示数组中的数字数量和数组中数字的最大值。

输出格式

输出一个整数,即元素个数为 nn 且所有数字不超过 cc 的好数组的数量。由于结果可能非常大,请将答案对 998244353998244353 取模后输出。

3 3

7

2 6

14

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 00 是样例。

子任务 分值 附加限制 子任务依赖 备注
11 1515 n10n \leq 10c10c \leq 10 00
22 1414 n1000n \leq 1000c1000c \leq 1000 0,10, 1
33 1212 n5000n \leq 5000c5000c \leq 5000 020 \sim 2
44 1616 n100000n \leq 100000c100000c \leq 100000 030 \sim 3
55 1414 n106n \leq 10^{6}c106c \leq 10^{6} 040 \sim 4
66 1515 n107n \leq 10^{7}c107c \leq 10^{7} 050 \sim 5
77 1414 060 \sim 6