훈련소로 가는 날

훈련소로 가는 날 욱제는 문득 떠올렸다. 훈련소가 논산에 있는 이유는 무엇일까? 왜 why?

그것은 바로…

논산(non-산)은 산이 아니기 때문이다. 길이가 3인 수열 $a_1, a_2, a_3$가 산임은 $a_1 < a_2 > a_3$임을 의미한다. 어떤 수열이 논산임은 수열의 인접한 세 항이 산인 경우가 없음을 의미한다. 다시 말해, 길이 $N$의 수열 $a$에 대해 $2 \le i < N$이고 $a_{i-1} < a_i > a_{i+1}$인 경우가 없다.

논산인 수열이 몇 개가 있는지 알아보자.

첫째 줄에 $N$과 $M$이 주어진다.

$1$ 이상 $M$ 이하의 정수로 이루어진 길이 $N$의 수열 중 논산인 것의 개수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

• $1 \le N \le 1\,000$
• $1 \le M \le 100$