题目描述

给定整数 $N,\ K$。

当长度为 $K$ 的整数序列 $a=[a_1,\ a_2,\ \ldots,\ a_K]$ 满足对于所有 $1 \leq i \leq K$，都有 $1 \leq a_i \leq i$ 时，称 $a$ 为好序列。

当长度为 $NK$ 的整数序列 $b=[b_1,\ b_2,\ \ldots,\ b_{NK}]$ 满足以下条件时，称 $b$ 为优秀序列：存在一种将 $b$ 分解为 $N$ 个长度为 $K$ 的（不一定连续的）子序列的方法，使得每个子序列都是好序列。

定义 $f(pos,\ val)$ 为满足 $b_{pos}=val$ 的优秀序列 $b$ 的个数。

请你对于所有 $1 \leq pos \leq NK$，$1 \leq val \leq K$，求出 $f(pos,\ val)$。由于这些数可能非常大，请输出它们对素数 $P$ 取模的结果。

输入格式

输入从标准输入中给出，格式如下：

$N$ $K$ $P$

输出格式

输出共 $NK$ 行。第 $i$ 行的第 $j$ 个数为 $(f(i,\ j) \bmod P)$。

样例 1

输入

2 2 965166677

输出

6 0 
4 2 
4 2 
3 3

说明/提示

限制

• $1 \leq N \leq 20$
• $1 \leq K \leq 20$
• $10^8 \leq P \leq 10^9$
• $P$ 是素数。

样例解释 1

存在以下 $6$ 个优秀序列。

• $[1, 1, 1, 1]$：可以分为 $[b_1, b_2], [b_3, b_4]$。
• $[1, 1, 1, 2]$：可以分为 $[b_1, b_2], [b_3, b_4]$。
• $[1, 2, 1, 1]$：可以分为 $[b_1, b_2], [b_3, b_4]$。
• $[1, 2, 1, 2]$：可以分为 $[b_1, b_2], [b_3, b_4]$。
• $[1, 1, 2, 1]$：可以分为 $[b_1, b_3], [b_2, b_4]$。
• $[1, 1, 2, 2]$：可以分为 $[b_1, b_3], [b_2, b_4]$。

由 ChatGPT 4.1 翻译