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 KN 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 109+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 109+7 in a single line.
Constraints
1 ≤ L ≤ N ≤ 3333
0 ≤ T ≤ N - L + 1
1 ≤ K ≤ 109
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}.
