题目内容

小塔是一位《原神》的全勤玩家，但她却抢不到《原神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