All Tracks Algorithms Dynamic Programming Problem

MINION TROUBLE
Tag(s):

Medium

Problem
Editorial
Analytics

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.

SAMPLE INPUT
4 2 1 1
SAMPLE OUTPUT
8
Explanation

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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications