We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- Practice
- Mathematics
- Combinatorics
- Parity Party

# Parity Party

# Parity Party

We need your help to divide candies at a very unusual party!

There are different candies in total. There are three kinds of people at party:

- of them want to get
*odd*number of candies, - of them want to get
*even*number of candies, - simply don't care about parity of candies they get.

Find out the number of ways to divide all of candies between everybody ( people), such that everyone is satisfied. Some people may not receive a candy.

**Input Format**

One line of input contains four space-separated integers .

**Constraints**

- ,
- ,
- .

**Output Format**

Print one line containing answer to the problem modulo .

**Sample Input 0**

```
3 1 1 0
```

**Sample Output 0**

```
4
```

**Explanation 0**

Let be three different candies. One of the visitors wants to get odd number of candies, the other wants to get even number. There are four good splittings:

.