TheAnimalProgrammingCompetitions

Problem Statement

Cat Taro and rabbit Hanako are running the animal programming competitions in a forest. John and Brus are invited as judges. Each team that takes part in the competitions consists of exactly four members. Each team member is either a cat or a rabbit. You are given a int[] rabbits. The number of teams that take part in the competitions is equal to the number of elements in rabbits. For each i, team number i (0-based index) consists of rabbits[i] rabbits and 4-rabbits[i] cats.

According to the best traditions of the animal programming competitions, each rabbit brings one carrot at the opening ceremony and presents it to some participant (either a cat or a rabbit) from a different team. The rabbits always coordinate their choices in order to make sure that no participant receives more than one carrot as a present. It seems this task is not that easy for the rabbits, so they asked the judges (John and Brus) to help them. Now John and Brus are thinking of a carrot distribution plan. All the carrots are considered pairwise distinct. Hence, two distribution plans are considered distinct if and only if there is at least one participant that receives a different present (i.e., either a different carrot in each plan, or a carrot in one plan and no carrot in the other). Return the number of different distribution plans, modulo 1,234,567,891.

Definition

Class:: TheAnimalProgrammingCompetitions
Method:: find
Parameters:: int[]
Returns:: int
Method signature:: int find(int[] rabbits)
(be sure your method is public)

Constraints

rabbits will contain between 1 and 47 elements, inclusive.
Each element of rabbits will be between 0 and 4, inclusive.

Examples

```
{0, 1, 0}
```
```
Returns: 8
```
There are eight options for the only rabbit in the competitions.
```
{4}
```
```
Returns: 0
```
Rabbits can't present carrots to their teammates.
```
{1, 1, 0}
```
```
Returns: 60
```
If the first rabbit presents their carrot to somebody from the second rabbit's team then there are eight options for the second rabbit, if not - only seven. Thus the total number of different plans is 4*8 + 4*7 = 60.
```
{0, 1, 2, 3, 4}
```
```
Returns: 644027397
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.