Description

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...

Input Format

Two integers $n,k$.

Output Format

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

1 1926

2

23 3

509581943

1919 810

252250482

Hint

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