eolymp
bolt
Try our new interface for solving problems
Problems

Трійки

Трійки

Дано поле $n \times m$. Рядки нумерують зверху вниз від $1$ до $n$. Стовпці нумеруються зліва направо з $1$ до $m$. Деякі клітинки білі, а всі інші~--- чорні. Введемо масив $a$ довжиною $n$, а також масиви $b$ та $c$ довжиною $m$, вони будуються наступним чином: \begin{itemize} \item $a_i$ ($1 \leq i \leq n$)~--- мінімальне $j$ таке, що клітинка $(i, j)$ чорна, або $m+1$, якщо такої немає; \item $b_i$ ($1 \leq i \leq m$)~--- мінімальне $k$ таке, що клітинка $(k, i)$ чорна, або $n+1$, якщо такої немає; \item $c_i$ ($1 \leq i \leq m$)~--- максимальне $k$ таке, що клітинка $(k, i)$ чорна, або $0$, якщо такої немає. \end{itemize} Скільки трійок різних масивів $(a, b, c)$ може бути? Знайдіть відповідь за модулем $998244353$. \InputFile Перший рядок містить два цілі числа $n$ та $m$ ($1 \leq n \leq 8\,000$, $1 \leq m \leq 200$). \OutputFile Виведіть відповідь за модулем $998244353$.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
2 3
Output example #1
64
Input example #2
4 3
Output example #2
2588
Input example #3
17 13
Output example #3
229876268
Input example #4
5000 100
Output example #4
57613837
Author Anton Tsypko