#P18481. Growing Sequences

Growing Sequences

Growing Sequences

科学研究中经常会出现指数增长的序列。一些研究者关心长度为 nn 的整数数组,要求每个元素都至少是前一个元素的两倍,即

2ai≤ai+1(1≤i<n).2a_i\le a_{i+1}\qquad(1\le i<n).

请计算满足此条件,且每个元素都在 11 到 cc 之间的不同数组的数量。由于答案可能很大,输出它对 998 244 353998\,244\,353 取模的结果。

输入格式

输入只有一行,包含两个整数 n,cn,c(1≤n≤601\le n\le60,1≤c≤10181\le c\le10^{18}),分别表示数组长度和元素上界。

输出格式

输出一个整数:满足全部条件的数组数量,对 998 244 353998\,244\,353 取模。

原样例

1 5
5
3 6
4
15 179
0
35 1234567887654321
576695683

样例说明

第一组样例中,有 55 个不同数组:[1],[2],[3],[4],[5][1],[2],[3],[4],[5]。

第二组样例中,有 44 个不同数组:[1,2,4],[1,2,5],[1,2,6],[1,3,6][1,2,4],[1,2,5],[1,2,6],[1,3,6]。

第三组样例中,不存在满足条件的数组。