J. The Set Terminator
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mohannad's hobby involves inventing pointless machines for enjoyment. Today, he invented the set terminator machine.

Before he starts the set terminator, Mohannad chooses three integer numbers $$$m$$$, $$$k$$$ and $$$q$$$ as a preset. Mohannad would then provide the set terminator with a set $$$s$$$ of $$$n$$$ integer numbers (not necessarily distinct), all between $$$1$$$ and $$$m$$$.

Once Mohannad turns on the set terminator, it will generate an array $$$a$$$ of $$$q$$$ integer numbers, where $$$1 \le a_i \le m$$$. The set terminator would then do $$$q$$$ operations, in the $$$i$$$-th operation, it will do the following:

  • The set terminator will add $$$a_i$$$ to the set.
  • The set terminator will then terminate (I.e. remove) the $$$k$$$-th smallest integer number in the set. For example, if the set contains the integer numbers $$$\{1, 2, 2, 4\}$$$ and $$$k=3$$$, the set terminator will remove a $$$2$$$ and the set will be $$$\{1, 2, 4\}$$$.

After the set terminator is done working, it will print the sum of all of the integer numbers of the set on its screen.

As Mohannad does not really know what are the values of the array $$$a$$$, he is interested in finding the sum of answers printed on the screen of the set terminator in all of the $$$m^q$$$ ways to generate the array $$$a$$$. As this might take forever, can you help Mohannad?

Input

The first line of the input contains four space-separated integer numbers $$$n$$$, $$$m$$$, $$$q$$$ and $$$k$$$ $$$(1 \le n, m, q \le 1000, 1 \le k \le n+1)$$$. The number of integer numbers of the set Mohannad will provide to the set terminator, the maximum limit of each number in the set, the number of operations the set terminator will do on the set and the index of the integer number that will be terminated, respectively.

The second line of the input contains $$$n$$$ space-separated integer numbers $$$s_1, s_2 \dots s_n$$$ $$$(1 \le s_i \le m)$$$, the initial elements of the set before it is provided to the set terminator.

Output

Print a single line containing a single integer number. The sum of answers printed on the screen of the set terminator in all of the $$$m^q$$$ ways to generate the array $$$a$$$. Since the answer might be large, print the answer modulo $$$10^9+7$$$.

Examples
Input
3 4 2 1
2 4 4
Output
179
Input
5 10 3 2
9 4 6 6 8
Output
34493