#P13541. [OOI 2022] Good arrays

    ID: 15417 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>2022排列组合筛法Moscow Olympiad

[OOI 2022] Good arrays

Problem Description

Recently Vasya learned about integer division. Inspired by this sacred knowledge, he decided to learn more about arrays of positive integers which satisfy some divisibility conditions. More precisely, Vasya calls an array a={a1,a2,…,an}a=\{a_1,a_2,\ldots,a_n\} good\textit{good} iff for every ii from 11 to n−1n-1, aia_i is divisible by ai+1a_{i+1}. Please help him count the number of good arrays of length nn consisting of integer numbers not greater than cc.

Input Format

The only input line contains two integers nn and cc (1≤n,c≤5⋅1071 \le n, c \le 5 \cdot 10^7) --- the length of the array and the maximum allowed value.

Output Format

Output a single integer --- the total number of good arrays of length nn consisting of positive integers not greater than cc. As this number might be quite large, please output its remainder modulo 998 244 353998\,244\,353.

3 3
7
2 6
14

Hint

The testset for this problem consists of 7 test groups. You get points for a group only if your solution passes all tests from this group and from all the required groups.

Offline-evaluation\textbf{Offline-evaluation} means that you will not get immediate feedback for this group and you will be able to see the outcome only after the end of the competition.

Group Points Additional constraints < Required groups Comment
nn cc
0 00 -- Sample test cases.
1 1515 n≤10n \le 10 c≤10c \le 10 00
2 1414 n≤1000n \le 1000 c≤1000c \le 1000 0,10, 1
3 1212 n≤5000n \le 5000 c≤5000c \le 5000 00--22
4 1616 n≤100 000n \le 100\,000 c≤100 000c \le 100\,000 00--33
5 1414 n≤106n \le 10^6 c≤106c \le 10^6 00--44
6 1515 n≤107n \le 10^7 c≤107c \le 10^7 00--55
7 1414 -- 00--66 Offline-evaluation.