题目描述

对于一个长度为 $n$ 的排列 $a$，定义一个排序算法 $A(k)$ 如下：

• 执行 $k$ 轮如下操作：
  • 依次从 $1\sim n-1$ 枚举 $i$：
    • 若 $a_i>a_{i+1}$，则交换 $a_i$ 和 $a_{i+1}$。

给定 $n$ 和 $k$，求出有多少个长度为 $n$ 的排列 $a$ 执行如上排序算法 $A(k)$ 后对于任意满足 $1\leq i<n$ 的 $i$ 均满足 $a_i<a_{i+1}$，答案对 $998244353$ 取模。

输入格式

共一行两个数 $n,k$，意义同题目描述。

输出格式

输出一个非负整数表示符合条件的排列的个数，对 $998244353$ 取模。

4 5

24

3 1

4

30 1

536870912

99 37

286701794

1000000000000000000 1919810

235483917

提示

【样例解释 #1】

所有的排列都符合要求。

该样例满足测试点 $7$ 的限制。

【样例解释 #2】

在所有的排列中，有以下排列满足要求。

$[1,2,3],[1,3,2],[2,1,3],[3,1,2]$。

所以答案为 $4$。

该样例满足测试点 $14$ 的限制。

【数据范围】

对于所有测试数据：$1\leq n\leq 10^{18}$，$1\leq k\leq 2\times 10^7$。

对于测试点 $1\sim 10$：$k>n$。

对于测试点 $11\sim 65$：$k\leq n\leq 10$。

对于测试点 $66\sim 80$：$n\leq 100$，$k=1$。

对于测试点 $81\sim 90$：$n\leq 100$。

对于测试点 $91\sim 95$：$n\leq 10^7$。

对于测试点 $96\sim 100$：无特殊性质。