[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 1926

2

23 3

509581943

1919 810

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 **此题稍有卡常，请注意优化代码常数。**