Good arrays

시간 제한2초메모리 제한1024 MB

요약
각 원소가 다음 원소로 나누어떨어지고 값이 c 이하인 길이 n 배열의 개수를 998244353으로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
정수론, 동적 계획법, 조합론
정답자
아직 제출이 없습니다

문제

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=a_1,a_2,…,a_na=\\{a\_1,a\_2,\ldots,a\_n\\} good iff for every ii from 11 to n−1n-1, a_ia\_i is divisible by a_i+1a\_{i+1}. Please help him count the number of good arrays of length nn consisting of integer numbers not greater than cc.

입력

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 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.

예제2

  1. 예제 1

    입력
    3 3
    
    예상 출력
    7
    
  2. 예제 2

    입력
    2 6
    
    예상 출력
    14