Growing Sequences

시간 제한1초메모리 제한2048 MB

요약
각 원소가 1 이상 c 이하이고 이전 원소의 두 배 이상인 길이 n 배열의 개수를 998244353으로 나눈 나머지를 구한다.
난이도

어려움10점 중 9점

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

문제

In scientific research, exponentially growing sequences appear quite often. Some researches are especially interested in integer arrays of length nn where each element is at least twice as large as the previous one: formally, 2⋅a_i≤a_i+12 \cdot a\_{i} \le a\_{i+1} for 1≤i≤n−11 \leq i \leq n - 1. They want to calculate the number of different bounded arrays satisfying this condition.

Help them! Count the number of such arrays consisting of integers from 11 to cc. Since this number can be very large, you should output it modulo 998,244,353998\\,244\\,353.

입력

The only line contains two integers nn and cc (1≤n≤601 \le n \le 60; 1≤c≤10181 \le c \le 10^{18}): the length of the arrays and the maximum value of their elements.

출력

Output the number of different arrays modulo 998,244,353998\\,244\\,353.

힌트

In the first example, there are 55 different arrays: \[1]\[1], \[2]\[2], \[3]\[3], \[4]\[4], \[5]\[5].

In the second example, there are 44 different arrays: \[1,2,4]\[1, 2, 4], \[1,2,5]\[1, 2, 5], \[1,2,6]\[1, 2, 6], \[1,3,6]\[1, 3, 6].

In the third example, there are no arrays satisfying the conditions.

예제4

  1. 예제 1

    입력
    1 5
    
    예상 출력
    5
    
  2. 예제 2

    입력
    3 6
    
    예상 출력
    4
    
  3. 예제 3

    입력
    15 179
    
    예상 출력
    0
    
  4. 예제 4

    입력
    35 1234567887654321
    
    예상 출력
    576695683