Growing Sequences

Time limit1sMemory limit2048 MB

Summary

Count arrays of length n where each element is at least twice the previous one and all values lie between 1 and c, modulo 998244353.

Level: Medium6 of 10
Topics: Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

Exponentially growing sequences appear often in scientific research. Some researchers are especially interested in integer arrays of length $n$ where each element is at least twice the previous one. Formally, $2 \cdot a_i \le a_{i+1}$ holds for every $1 \le i \le n-1$ . Count the number of such arrays whose elements are integers from $1$ to $c$ . The count can be very large, so output it modulo $998\,244\,353$ .

Input

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

Output

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

Hint

In the first example, there are $5$ different arrays: [1], [2], [3], [4], [5]. In the second example, there are $4$ different arrays: [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 6]. In the third example, there are no arrays satisfying the conditions.

Examples4

Example 1
Input
```
1 5
```
Expected output
```
5
```
Example 2
Input
```
3 6
```
Expected output
```
4
```
Example 3
Input
```
15 179
```
Expected output
```
0
```
Example 4
Input
```
35 1234567887654321
```
Expected output
```
576695683
```