题目背景

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

题目描述

小 F 有一个奇妙的数组 $a$，$a$ 中没有重复的元素，长度为 $n$，他使用std::sort将他排序了，认为它是有序的，所以他正在使用这样的方法进行二分查找。显然，能否查到只和数列的离散化结果有关，所以你可以直接把 $a$ 看作 $1\sim n$ 的一个排列。

int search(int key) {
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (a[mid] < key)
      l = mid + 1;
    else if (a[mid] == key)
      return mid;
    else
      r = mid - 1;
  }
  return -1;
}

不幸的是，小 W 为了让他戒掉万能头，在bits/stdc++.h中写了#define sort random_shuffle，这意味着 $a$ 实际是一个随机的排列。

现在，对于所有在 $1$ 到 $N$ 范围内的 $n$，以及所有在 $1$ 到 $n$ 范围内的 $k$，在 $a$ 数列的所有排列中，有几个可以正确地找到第 $k$ 小的元素 $key$（即返回值非 $-1$）？由于答案可能过大，请输出它对给定模数 $p$ 取模的结果。

输入格式

一行两个正整数 $p,N$。

输出格式

$N$ 行，第 $n$ 行 $n$ 个正整数，代表在 $n$ 个元素中找 $k$ 能找到的方案数。

998244353 5

1
1 2
4 4 4
12 12 14 18
48 54 60 66 72

提示

数据范围

本题采用 Subtask 评测。

• Subtask 1（$10$ pts）：$N=10$，$p\ge998244352$；
• Subtask 2（$25$ pts）：$N=100$，$p\ge1009$ 且为素数；
• Subtask 3（$25$ pts）：$N=400$，$p\ge1009$ 且为素数；
• Subtask 4（$40$ pts）：$N=400$。

对于所有数据，$10\le N\le 400$，$2\le p\le998244353$。