Bob is playing a new game that he has discovered over March Break. To play the game, he has bought a ~K~-sided die with faces numbered ~1~ to ~K~ which he must roll ~N~ times in a row. Bob succeeds on the ~i~th roll if the number he rolls is at least ~a_i~.

In order to increase the number of rolls that he succeeds, Bob will use his portent ability inside the game which will allow him to replace up to two of the rolls with two values that he had rolled beforehand, ~X~ and ~Y~. Note that Bob may only choose to replace a roll after rolling the die for that roll.

Bob would like to know the number of possible dice roll configurations, out of a total of ~K^N~, such that he can succeed on all ~N~ rolls with optimal use of his ability. Since this number may be very large, Bob would like to know its value modulo ~10^9+7~.

Input Specifications

The first line will contain two space-separated integers, ~N~ ~(1 \le N \le 10^5)~ and ~K~ ~(1 \le K \le 10^5)~.

The next line will contain two space-separated integers, ~X~ and ~Y~ ~(1 \le X, Y \le K)~.

The next line will contain ~N~ space-separated integers, ~a_1, a_2, ..., a_N~ ~(1 \le a_i \le K)~.

Subtask 1 [30%]

~1 \le N \le 10^4~

Subtask 2 [70%]

No further constraints.

Output Specifications

Output one integer, the number of possible dice configurations such that Bob can succeed on all ~N~ rolls, modulo ~10^9 + 7~.

Sample Input 1

3 3
2 3
2 3 3

Sample Output 1

15

Sample Input 2

5 20
8 20
9 15 12 19 5

Sample Output 2

368640