수열 생성하기

정수 수열의 수열 $S$를 생각하자. 처음에 $S_0 = (1)$이다. 그다음 $S_1, S_2, \ldots, S_n$을 다음과 같이 만든다.

$|S_i|$를 수열 $S_i$의 길이, $s_{i,j}$를 $S_i$의 $j$번째 원소라고 하자. 그러면 $S_{i+1}$의 길이는 $|S_i|+1$이고, $S_i$에서 다음 두 연산 중 하나로 얻을 수 있다.

• 새 수열의 $|S_i| + 1$번째 원소로 $1$ 또는 주어진 정수 $m$을 쓴다.
• 인덱스 $j$ ($1 \le j < |S_i|$)를 골라 $s_{i,j} < x < s_{i,j + 1}$ 또는 $s_{i,j} > x > s_{i,j + 1}$인 정수 $x$를 선택하고, $s_{i,j}$와 $s_{i,j+1}$ 사이에 넣는다. 오른쪽 부분의 인덱스는 $1$씩 밀린다.

$n$과 $m$이 주어질 때, 서로 다른 수열의 순서쌍 $S_1 \ldots S_n$의 개수를 구하자. 두 순서쌍은 $1$ 이상 $n$ 이하의 어떤 $i$에 대해서라도 $S_i$가 다르면 서로 다르다고 본다. 답이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.

입력은 한 줄로 이루어지며, 두 정수 $n$과 $m$이 주어진다. ($1 \le n \le 3000$, $2 \le m \le 10^8$)

서로 다른 수열의 순서쌍 $S$의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 번째 예제에서 가능한 순서쌍은 다음과 같다.

• $S_1=(1,3)$ (첫 번째 연산), 그다음 $S_2=(1,2,3)$ (두 번째 연산);
• $S_1=(1,1)$ (첫 번째 연산), 그다음 $S_2=(1,1,3)$ (첫 번째 연산);
• $S_1=(1,1)$ (첫 번째 연산), 그다음 $S_2=(1,1,1)$ (첫 번째 연산);
• $S_1=(1,3)$ (첫 번째 연산), 그다음 $S_2=(1,3,3)$ (첫 번째 연산);
• $S_1=(1,3)$ (첫 번째 연산), 그다음 $S_2=(1,3,1)$ (첫 번째 연산).

따라서 답은 $5$이다.