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.
  1. Practice
  2. Mathematics
  3. Combinatorics
  4. 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:
.