23109번 - Generate the Sequences 다국어

문제

Consider $S,ドル the sequence of integer sequences. Initially, $S_0 = (1)$. After that, we construct $S_1, S_2, \ldots, S_n$ as follows.

Let $|S_i|$ be the length of the sequence $S_i,ドル and $s_{i,j}$ be the $j$-th element of $S_i$. Then $S_{i+1}$ will have length $|S_i|+1$ and can be obtained from $|S_i|$ using one of the following two operations:

• Write 1ドル$ or the given integer $m$ as the element with number $|S_i| + 1$ of the new sequence.
• Select an index $j$ (1ドル \le j < |S_i|$), choose integer $x$ such that $s_{i,j} < x < s_{i,j + 1}$ or $s_{i,j} > x > s_{i,j + 1},ドル and place it between $s_{i,j}$ and $s_{i,j+1},ドル shifting the right part's indices by 1ドル$.

Given $n$ and $m,ドル find the number of different ordered sets of sequences $S_1 \ldots S_n$. Two sets are considered different if, at least for one $i$ from 1ドル$ to $n,ドル the sequences $S_i$ in those sets differ. As the answer may be too large, print it modulo 998ドル,244円,353円$.

입력

The input consists of one line containing two integers $n$ and $m$ (1ドル \le n \le 3000,ドル 2ドル \le m \le 10^8$).

출력

Print the number of different sequences $S$ modulo 998ドル,244円,353円$.

제한

힌트

Here are the possible sequences in the first example:

• $S_1=(1,3)$ (first operation), then $S_2=(1,2,3)$ (second operation);
• $S_1=(1,1)$ (first operation), then $S_2=(1,1,3)$ (first operation);
• $S_1=(1,1)$ (first operation), then $S_2=(1,1,1)$ (first operation);
• $S_1=(1,3)$ (first operation), then $S_2=(1,3,3)$ (first operation);
• $S_1=(1,3)$ (first operation), then $S_2=(1,3,1)$ (first operation).

Therefore, the answer is 5ドル$.