题目大意

一共有q+1个人跟你抢票，有些人可以抢两种票，有一些只能抢第二组票，求出你能抢到票的排列组合数量

思路

预处理组合数和排列数： 由于数据量较大（最大到3000），可以使用杨辉三角预处理出组合数 C(n, m) 和排列数 A(n, m)，以便在后续计算中快速查询。

分配抢票玩家： 将抢票玩家分为两类：可以抢两档票的玩家（天数 <= t）和只能抢第二档票的玩家（天数 > t）。统计这两类玩家的数量分别为 n1 和 n2。

枚举抢票情况：

题目内容

米小游是一位《原神》的全勤玩家，但她却抢不到《原神FES》的门票，因此决定开发一款有利于全勤玩家的抢票系统。

新的抢票系统如下：将票分成$2$个档位，每个档位的票数都为 $m$，游戏运营了 $n$天，设置一个抢票参数 $t$。

抢票玩家的游戏登陆天数为 $x$，若 $x ≤ t$，则优先分配第$1$档位的票，若第$1$档位已经没有票了，则分配第 $2$档位的票，若第$2$档位也没有票，则此玩家没有抢到票；若 $x > t$，则玩家只能分配第$2$档位的票，若第$2$ 档位没有票，则此玩家没有抢到票。

米小游是全勤玩家，登陆天数为 $n$。现在有$q$个玩家在和米小游抢票，第$i$个玩家的登陆天数为$d_i$。抢票的先后顺序可以看成是一个长度为$q+1$的排列，但具体的排列未知。

米小游想知道有多少种排列可以使得她至少抢到一张票。

输入描述

第一行输入四个整数：

$n, m, q, t$($1 ≤ n, m, q ≤ 10^3, 1 ≤ t ≤ n$)：表示游戏运营天数、每个档位的票数、抢票玩家数、抢票参数。

第二行输入$q$整数 $d_i$($1 ≤ d_i ≤ n$)：表示玩家的游戏登陆天数。

输出描述

输出一个整数，表示答案。由于这个数字可能很大，因此需要输出这个数字对$10^9 + 7$取模后的结果。

样例1

输入

2 1 2 2
1 2

输出

4