题目描述

In his recent work on permutation properties, $\texttt{Dr.Z}$ investigates the relationship between element values and their indices. A key focus is the cardinality of the set of indices $i$ where $p_i>i$ (called $\bf{larger\ position}$) and where $p_i<i$ (called $\bf{smaller\ position}$). To formalize this, he defines $f(n,x,y)$ as the number of permutations of $n$ elements containing exactly $x$ larger positions and $y$ smaller positions. $\texttt{Dr.Z}$ now aims to characterize this function completely by determining the values of $f(n,x,y)$ across all valid positive integers $x$ and $y$ after modulo $m$. Could you help him solve this problem efficiently?

输入格式

The only line contains two integers $n,m(2\le n\le 2000,2\le m\le 10^9+7)$.

输出格式

There are $n-1$ rows in total. The $i$-th row contains $n-i$ integers. The $j$-th integer represents the result of $f(n,i,j)$ modulo $m$.

5 998244353

10 10 5 1
10 35 21
5 21
1

提示

The five permutations of $x=1,y=3$ are $[1,5,2,3,4], [4,1,2,3,5], [5,1,2,4,3], [5,1,3,2,4]$, and $[5,2,1,3,4]$.