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.
One line of input contains four space-separated integers .
Print one line containing answer to the problem modulo .
Sample Input 0
3 1 1 0
Sample Output 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: