AT_kupc2020_b Numbers on Papers

有 $N$ 张编号从 $1$ 到 $N$ 的纸，每张纸上各写有 $K$ 个整数。 第 $i$ 张纸上写的整数为 $v_{i,1},\ v_{i,2},\ \ldots,\ v_{i,K}$。 现在要从每张纸上各自独立地选出一个整数，组成一个数列，使得第 $i$ 项为从第 $i$ 张纸上选出的整数。 这样的数列共有 $K^N$ 种可能，其中有多少种是广义单调递增的？由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。 这里，数列 $A=(a_1,\ a_2,\ \ldots,\ a_N)$ 被称为广义单调递增，是指对于所有 $i\ (1 \leq i \leq N-1)$，都有 $a_i \leq a_{i+1}$。

输入按以下格式从标准输入读入。 > $N$ $K$ $v_{1,1}$ $v_{1,2}$ $\cdots$ $v_{1,K}$ $v_{2,1}$ $v_{2,2}$ $\cdots$ $v_{2,K}$ $\vdots$ $v_{N,1}$ $v_{N,2}$ $\cdots$ $v_{N,K}$

请输出满足题意的广义单调递增数列的种数，对 $10^9+7$ 取模。

### 限制条件 - $1 \leq N \leq 100$ - $1 \leq K \leq 10000$ - $1 \leq v_{i,1} < v_{i,2} < \cdots < v_{i,K} \leq 10^9\ (1 \leq i \leq N)$ - 输入均为整数。 ### 样例解释 1 所有可能的数列如下，共 $4$ 种： - $(2,1)$ - $(2,5)$ - $(4,1)$ - $(4,5)$ 其中广义单调递增的有 $(2,5)$ 和 $(4,5)$，所以答案是 $2$。 ### 样例解释 2 也有可能无论如何选都无法组成广义单调递增的数列。 ### 样例解释 3 请注意输出时要对 $10^9+7$ 取模。 由 ChatGPT 4.1 翻译