One day, The well known female Monk also known as Munki, was meditating at the forest. But a minion came and disturbed Munki from her meditation. Now, Munki has decided to curse the minion. The minion got frightened and cried. Now, seeing the cute minion melted the monk's heart and she offered the minion a deal Minion is given a question and minion needs to answer the question else it is trouble on hand. The question is : Minion will be given a single query each containing four integers N,K,L and V. Now the minion needs to find the number of solutions to this equation:
(a0 + a1 + a2 ................... +an-1) mod K = V
Where 0<=ai<=L
Input
Only single line of Input contains four integers, N,K,L and V.
Output
Output a single line containing the number of solutions to above equation.
Input Constraints:
1<=N<=10^9
1<=K<=100
1<=L<=10^9
0<=V<=K-1
Note: There are N integers, a0 to an-1, and each is a whole number maximum upto L.
Here N=4 K=2, L=1 and V=1
All possible combinations of permutations are:
(0+0+0+0)=0 mod 2 =0
(0+0+0+1)=1 mod 2 =1 - 1
(0+0+1+0)=1 mod 2 =1 - 2
(0+0+1+1)=2 mod 2=0
(0+1+0+0)=1 mod 2=0 - 3
(0+1+0+1)=2 mod 2=0
(0+1+1+0)=2 mod 2=0
(0+1+1+1)=3 mod 2=1 - 4
(1+0+0+0)=1 mod 2=1 - 5
(1+0+0+1)=2 mod 2=0
(1+0+1+0)=2 mod 2=0
(1+0+1+1)=3 mod 2=1 - 6
(1+1+0+0)=2 mod 2=0
(1+1+0+1)=3 mod 2=1 - 7
(1+1+1+0)=3 mod 2=1 - 8
(1+1+1+1)=4 mod 2=0
answer =8
