Problem Background

In Gensokyo, the cherry blossoms of the netherworld bloom year after year.

In Yuyuko's heart, a cherry tree has appeared, a sequence closely related to flowers, and a poignant question.

Where are those OIers who once strived now?

Problem Description

In Gensokyo, Yuyuko, the West Mansion's Yuyuko, is a renowned gluttonous spirit who possesses the ability to manipulate death.

Through an external shikigami—a computer, Yuyuko has conducted profound research on OI and discovered some astonishing facts:

• OIers have given up many things that their peers possess, seeking their dreams in the sea of problems.
• However, those who have AFOed (Abandoned Further Optimization) are no different from the dead. They may have lost their dreams...

At this moment, Yuyuko noticed that the cherry blossoms dancing in the sky formed two integers, $n$ and $k$. Simultaneously, beneath 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 calculate $f(n,k) \bmod 998244353$, as she believes this function symbolizes OIers...

Input Format

Two integers $n, k$.

Output Format

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

Sample Input and Output

Sample Input #1

1 1926

Sample Output #1

2

Sample Input #2

23 3

Sample Output #2

509581943

Sample Input #3

1919 810

Sample Output #3

252250482

Notes

Sample #1 Explanation

According to the definition, $f(1,1926)=2$.

Data Range and Constraints

This problem uses bundled testing.

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 data: $1\le n \le 10^{18}$, $0\le k \le 30000$

Problem Source

Lost Home 2019 Competition (MtOI2019) T6

Problem Author: NaCly_Fish
Problem Tester: Imagine
Problem Statement: disangan233

This problem has tight time constraints, please optimize your code accordingly.

见题面 Input 部分

见题面 Output 部分