P5519 [MtOI2019] Buried Bones in Hongchuan.

In Gensokyo, the cherry blossoms of the Netherworld bloom again and again, repeating year after year. In Yuyuko’s heart, there appeared a cherry tree, a sequence closely tied to blossoms, and a sad question. Those OIers who once struggled—where are they now?

In Gensokyo, Saigyouji Yuyuko (Yuyuko) is a ghost famous for being a big eater, and she has the power to control death. Through an external shikigami from the outside world—a computer—Yuyuko conducted deep research on OI, and discovered some shocking facts: * OIers gave up too many things that other classmates had, searching for their dreams in a sea of problems. * But for OIers who are AFO, what difference is there from death? Perhaps they have already lost their dreams... At this moment, Yuyuko found that the cherry blossoms dancing in the sky formed two integers $n$, $k$. Meanwhile, under the cherry tree, a description of a function $f(x,y)$ appeared: $$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}$$ Yuyuko wants you to compute $f(n,k) \bmod 998244353$. She believes this function symbolizes OIers...

Two integers $n,k$.

A positive integer $f(n,k) \bmod 998244353$.

[Sample $1$ Explanation] According to the definition, $f(1,1926)=2$. [Constraints and Notes] **This problem uses bundled testdata.** 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): No special restrictions. For $100\%$ of the testdata: $1\le n \le 10^{18}$, $0\le k \le 30000$. ### Source [Lost Home 2019 League](https://www.luogu.org/contest/20135) (MtOI2019) T6. Problem setter: NaCly_Fish. Problem reviewer: Imagine. Statement: disangan233. **This problem is slightly strict on time limits, so please optimize constant factors in your code.** Translated by ChatGPT 5