SP2815 INCSEQ - Increasing Subsequences

现有一个包含 $N$ 个整数的序列 $S_1, S_2, \ldots, S_N$（其中 $1 \le N \le 10,000$ 且 $0 \le S_i < 100,000$）。你需要计算出序列中有多少个长度为 $K$ 的递增子序列（满足 $1 \le K \le 50$ 且 $K \le N$）。具体来说，就是找出满足条件 $1 \le i_1 < i_2 < \cdots < i_K \le N$ 且 $S_{i1} < S_{i2} < \cdots < S_{iK}$ 的 $K$ 元组的数量。

第一行包含两个整数 $N$ 和 $K$，表示序列长度和子序列的长度要求。接下来的 $N$ 行，每行一个整数，按序列的顺序给出。

输出一个整数，表示长度为 $K$ 的递增子序列的数量，结果需要模 $5,000,000$。 **本翻译由 AI 自动生成**