SOLVE

LATER

MINION TROUBLE

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.

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++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"8000ab5": "/pagelets/show-submission/algorithm/minion-trouble-1/", "8000af2": "/pagelets/problem-author-tester/algorithm/minion-trouble-1/", "8000ada": "/pagelets/suggested-problems/algorithm/minion-trouble-1/", "8000b08": "/pagelets/problems-hint/algorithm/minion-trouble-1/", "8000b1d": "/pagelets/recommended-problems/algorithm/minion-trouble-1/"}

{}

realtime.hackerearth.com

80

96638c8bc93eebec8271966316dee0cfb83e88ae

58a29e5cae2309f04b28

/realtime/pusher/auth/