L. Larger or Smaller
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In his recent work on permutation properties, 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 \gt i$$$ (called larger position) and where $$$p_i \lt i$$$ (called 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. 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?

Input

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

Output

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$$$.

Example
Input
5 998244353
Output
10 10 5 1 
10 35 21 
5 21 
1
Note

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]$$$.