[MtOI2019] 埋骨于弘川
题目背景
在幻想乡中,冥界的樱花一年又一年地往复开放。
在 Yuyuko 的心中,出现了一棵樱花树,一个与花朵息息相关的序列,和一个伤感的问题。
那些曾经奋斗过的 OIer 们啊,如今又在何方呢?
题目描述
在幻想乡,西行寺 幽幽子(Yuyuko)是一个以贪吃著名的亡灵,她拥有操纵死亡的能力。
Yuyuko 通过外界的式神——电脑,对OI进行了深刻的研究 ,她发现了一些惊人的事实:
* OIer 们放弃了太多其他同学们拥有的东西,在题海中寻求自己的梦想。
* 但是 AFO 的 OIer 们,跟死亡又有什么区别呢?他们或许已经失去了自己的梦想……
这时幽幽子发现,天空中飘舞的樱花组成了两个整数 $n$,$k$。于此同时,在樱花树下,出现了一个函数 $f(x,y)$ 的描述:
$$f(x,y) = \begin{cases} 2 & , x=1 \\ 2^x& , 2\le x \le 42,y = 0 \\ \prod\limits_{i=1}^{42} f(x-i,y)^i & , x \ge 43,y = 0 \\ f(x-1,y)f(x,y-1) & , x\ge 2,y \ge 1\end{cases}$$
幽幽子想让你计算出 $f(n,k) \bmod 998244353$,她认为这个函数象征着OIer们......
输入输出格式
输入格式
两个整数 $n,k$
输出格式
一个正整数 $f(n,k) \bmod 998244353$
输入输出样例
输入样例 #1
1 1926
输出样例 #1
2
输入样例 #2
23 3
输出样例 #2
509581943
输入样例 #3
1919 810
输出样例 #3
252250482
说明
【样例 $1$ 解释】
根据定义,$f(1,1926)=2$。
【数据范围与约定】
**本题采用捆绑测试。**
Subtask 1 (7 points):$1\le n,k \le 1000$
Subtask 2 (11 points):$1\le n \le 10^{18}$,$k=0$
Subtask 3 (13 points):$1\le n \le 10^{18}$,$k=1$
Subtask 4 (29 points):$1\le n \le 10^{18}$,$0\le k \le 1000$
Subtask 5 (40 points):无特殊限制
对于 $100\%$ 的数据:$1\le n \le 10^{18}$,$0\le k \le 30000$
### 题目来源
[迷途之家2019联赛](https://www.luogu.org/contest/20135)(MtOI2019) T6
出题人:NaCly_Fish
验题人:Imagine
题面:disangan233
**此题稍有卡常,请注意优化代码常数。**