down

题目描述

近日，最牛刷题者下载了一款叫作 MatchUs 的交友软件，力求在预科期间完成脱单。

他一次性匹配了 $n$ 位女生。根据最牛刷题者的审美，每个女生有一个初始评分，第 $i$ 位女生的初始评分为 $a_i$ 。

为了让评分更加合理，最牛刷题者找了 $m$ 个室友。每个室友需要在 $n$ 位女生中选择 $v$ 位，最牛刷题者会让被选中的女生评分 $+1$ 。

最后，最牛刷题者会把女生按照评分从大到小排序，评分相等的女生间可以任意排序。然后他会选取一个 $1$ 到 $n$ 间的整数 $p$ ，并向前 $p$ 位女生发送约会申请。

他想知道有多少个可能的发送申请的方案。两个方案不同当且仅当：存在一个女生，她在一个方案中收到了申请，另一个方案中没有收到申请。答案对 $10^9+7$ 取模。

输入格式

第一行包含三个整数 $n,m,v$ 。

第二行包含 $n$ 个整数，第 $i$ 个整数代表 $a_i$ 。

输出格式

输出一行一个整数，表示答案对 $10^9+7$ 取模。

样例

样例输入1

3 1 2
1 2 3

样例输出1

5

样例解释1

可能的集合有 $\{2\},\{3\},\{1,3\},\{2,3\},\{1,2,3\}$ 。

样例 2~5

见下发文件。

数据范围

对于所有数据，保证 $2\le n,m\le 100,1\le v<n,0\le a_i\le 100$ 。

令 $V=\max a_i$ 。