18858번 - 훈련소로 가는 날

문제

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

그것은 바로…

논산(non-산)은 산이 아니기 때문이다. 길이가 3인 수열 a₁, a₂, a₃가 산임은 a₁ < a₂ > a₃임을 의미한다. 어떤 수열이 논산임은 수열의 인접한 세 항이 산인 경우가 없음을 의미한다. 다시 말해, 길이 N의 수열 a에 대해 2 ≤ i < N 이고 a_i-1 < a_i > a_i+1인 경우가 없다.

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 100

힌트