9155: IUPC

The International Unfair Programming Contest (IUPC) is a competition for cheating skills. In this competition, participants are required to solve as many problems as possible by cheating without drawing $\text{suspicion}$. As is known to all, Nan Xiang Institute of Science and Technology (NXIST) is one of the best cheaters in IUPC. They shot to fame by winning the gold medal in the IUPC Ningxia Railway Station, Yinchuang Site held in May 2020, where they successfully solved 6 problems.


You are the leader of IUPC team in NXIST, and your team is going to participate in IUPC Silk-Road Contest next week. There are $n$ problems in this contest, and participants have $t$ minutes to solve them. As a master cheater, you already know how to steal solutions submitted by others, so all your team need is to submit the stolen solutions without drawing $\text{suspicion}$ during the contest. Precisely, if problem $i$ is first solved by other team at the xix_ixi-th minute of the contest, your team will steal the solution $\text{immediately}$ and can submit it $\text{exactly once}$ at any time before the contest ends. However, to avoid $\text{suspicion}$, you set the following rules for your team:


Now you can predict the exact moment when each problem will be solved by other teams, that is, you know when your team can get the solution to each problem. Please calculate the number of different plans for your team to solve $\text{all}$ problems without drawing $\text{suspicion}$. Formally, a plan can be denoted as a sequence a1, a2, ..., ata_1,\ a_2,\ ...,\ a_ta1, a2, ..., at, where ai=pa_i=pai=p if your team submits the solution to problem $p$ in the $i$-th minute, or ai=0a_i=0ai=0 if your team does nothing in the $i$-th minute. Two plans are different if the sequences are different.

The first line contains four integers n, t, kn,\ t,\ kn, t, k and $m$ ($1\le n\le 13$, $1\le t\le 300$, 1≤k≤101\le k\le 101≤k≤10, $1\le m\le k$).
The second line contains $n$ integers x1, x2, ..., xnx_1,\ x_2,\ ...,\ x_nx1, x2, ..., xn (1≤xi≤t1\le x_i\le t1≤xi≤t), where xix_ixi denotes the moment when the problem $i$ is first solved by others.

Print an integer - the number of different plans for your team to solve all problems. Since the answer may be very large, you are required to print the value modulo 109+710^9 + 7109+7.

4 10 3 2
4 4 5 8

156

链接：https://ac.nowcoder.com/acm/contest/57364/F
来源：牛客网
For the second example, one of the valid plans can be denoted as follows:

Please note that all people, locations, and events mentioned above are entirely fictional. Any resemblance to actual people, places, or events is purely coincidental.