Background

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.

Problem Description

Little F has a magical array $a$. There are no duplicate elements in $a$, and its length is $n$. He sorted it using std::sort and believes it is ordered, so he is doing binary search in the following way. Obviously, whether it can be found only depends on the discretization result of the sequence, so you can directly treat $a$ as a permutation of $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;
}

Unfortunately, in order to make him quit the “universal header” (wan neng tou), Little W wrote #define sort random_shuffle in bits/stdc++.h, which means that $a$ is actually a random permutation.

Now, for all $n$ in the range $1$ to $N$, and for all $k$ in the range $1$ to $n$, among all permutations of the array $a$, how many of them can correctly find the $k$-th smallest element $key$ (i.e., the return value is not $-1$)? Since the answer may be too large, output it modulo the given modulus $p$.

Input Format

One line with two positive integers $p, N$.

Output Format

Output $N$ lines. Line $n$ contains $n$ positive integers, representing, among $n$ elements, the number of permutations for which searching for $k$ can succeed.

998244353 5

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

Hint

Constraints

This problem uses Subtask judging.

• Subtask 1 ($10$ pts): $N=10$, $p\ge998244352$;
• Subtask 2 ($25$ pts): $N=100$, $p\ge1009$ and is prime;
• Subtask 3 ($25$ pts): $N=400$, $p\ge1009$ and is prime;
• Subtask 4 ($40$ pts): $N=400$.

For all testdata, $10\le N\le 400$, $2\le p\le998244353$.

Translated by ChatGPT 5