In the computer world, a train of the length N can be represented as an array A of the same length. Such an array A contains integer elements between 1 and K, inclusive. Each element in A represents the quality of one carriage. Note that there are exactly K^N distinct trains.

Mike loves to travel and today he is going to do it with his friends. They want to occupy exactly L consecutive carriages. Of course, they want chosen L carriages to be of equal quality.

Someone saw a train and thus knows an array A. He said that there are exactly T ways for them to choose L consecutive carriages of equal quality. Now, Mike wants to know how many trains satisfy this description. Your task is to count them modulo 10⁹+7.

Input format

The only line of the input contains four space-separated integers N, L, T and K.

Output format

Find the number of trains satisfying the given description. Print it modulo 10⁹+7 in a single line.

Constraints

1 ≤ L ≤ N ≤ 3333
0 ≤ T ≤ N - L + 1
1 ≤ K ≤ 10⁹