Problem F
Ball Colors
Baby Timmy has a pool of balls that he plays with. The pool is made up of balls with $n$ different colors with a certain number of each color. Baby Timmy finds it interesting to order these balls in a line given certain conditions he made. Timmy has two conditions when playing his own game:
-
Balls of certain colors may not be next to each other
-
One particular sequence of colors which Timmy likes most must appear as many times as possible
Can you compute the total number of different ways in which Timmy can arrange his balls?
For instance, suppose Timmy has $2$ red, $1$ yellow, $2$ green, and $1$ blue ball(s). He doesn’t like for red or yellow balls to be next to each other, and his favorite sequence is “green blue.” The following six arrangements meet the requirements:
red green blue red green yellow red green blue yellow green red red green red green blue yellow red green yellow green blue red yellow green blue red green red yellow green red green blue red
This arrangement corresponds to Sample Input 1.
Note that Timmy insists on including his favorite sequence as often as the available balls allow, even if that means not being able to complete the arrangement of balls at all.
Input
The input consists of a single test case with three lines. The first line contains an integer $n$ ($2 \le n \le 50$), which describe the number of different colors. The remaining $n$ integers on that line denote how many balls Timmy has of each color (colors are numbered $1$ through $n$ and their frequencies appear in order). The number of balls he has of each color is between $1$ and $50$, inclusive.
The second line of input describes which colors Timmy does not want next to each other. The first integer $k$ ($0 \le k \le n$) gives the number of colors. This is followed by $k$ integers $c_ i$ ($1 \le c_ i \le n$) denoting the colors that prevent balls having any of these colors from being next to each other. Each $c_ i$ is unique.
The third line of input describes the sequence Timmy likes most. This first integer $l$ ($0 \le l \le n$) describes the length of this sequence, and the following $l$ integers $s_ i$ ($1 \le s_ i \le n$) describe the sequence that must appear as often as possible in the arrangement. Each $s_ i$ is unique and the sets $\{ c_ i \} $ and $\{ s_ i \} $ do not intersect.
Output
Output the number of arrangements Timmy can make that satisfy the given conditions. Since the number can be large, output its value modulo $1\, 000\, 000\, 007$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 1 2 1 2 1 2 2 3 4 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 1 1 1 1 2 2 3 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 2 2 3 1 1 2 2 3 |
18 |
| Sample Input 4 | Sample Output 4 |
|---|---|
3 1 2 3 2 1 2 0 |
12 |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 1 4 1 1 2 1 3 |
0 |
