4105. K元上升子序列

【题目背景】

【题目描述】

给定数列 $a_n$,求长度为 $k$ 的严格上升子序列的数量。

【输入格式】

第一行有两个整数 $n,k$,其中 $n$ 表示数列的长度。

接下来一行有 $n$ 个整数 $a_1,a_2 \dots  a_n$。

【输出格式】

输出答案对 $10^9+7$ 取模后的结果。

【样例输入】

5 3

1 2 2 3 4

【样例输出】

7

【样例说明】

在此键入。

【数据规模与约定】

对于其中 $30\%$ 的数据 $n \le 1000,k\le20,a_i \le 10^9$。

对于另外 $30\%$ 的数据 $n \le 10^5,k\le 20$,$a_i \le 10^5$。

对于 $100 \%$ 的数据 $n \le 10^5,k\le20,a_i \le 10^9$。

【来源】

在此键入。