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^9+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^9+7 in a single line.

Constraints
1 ≤ L ≤ N ≤ 3333
0 ≤ T ≤ N - L + 1
1 ≤ K ≤ 10^9

SAMPLE INPUT
5 2 1 2

SAMPLE OUTPUT
8

Explanation

For the sample test the only possible arrays are:
{1, 1, 2, 1, 2},
{1, 2, 1, 1, 2},
{1, 2, 1, 2, 2},
{1, 2, 2, 1, 2},
{2, 1, 1, 2, 1},
{2, 1, 2, 1, 1},
{2, 1, 2, 2, 1},
{2, 2, 1, 2, 1}.

见题面

见题面