Description

A group of classmates are playing a game with yyy.

Each time, they give yyy $n$ cards with numbers on them. All the numbers are "lucky numbers". Let the number on the $i$-th card be $a_i$.

On each move, yyy may choose to move forward $a_i$ steps and discard the $i$-th card. He wins when he has no cards left.

However, traps are set on positions that are "unlucky numbers". If yyy stops on such a cell, he loses. Note: even if he reaches the end, if that position is an unlucky number, he still loses.

Now, some classmates begin to ask: what is the probability that yyy will win?

They think this is a good question, and someone immediately asks yyy to write a program: "Computers are very fast! $24$ factorial is only $620\,448\,401\,733\,239\,439\,360\,000$, yyy, hurry up and write a program to compute it."

yyy is speechless. He says he does not want to compute the probability—at most he can compute the number of winning plans, and only modulo $10^9+7$.

None of them can code, so they have to compromise.

But now yyy is troubled: $24!$ is too large; it would take a long time to run.

He is seriously short on time and needs your help!

A number may belong to both the lucky numbers and the unlucky numbers.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers; the $i$-th integer is $a_i$, the number on the $i$-th card.

The third line contains an integer $m$ denoting the number of yyy's unlucky numbers (at most $2$).

If $m>0$, the fourth line contains $m$ integers $b_i$ representing all the unlucky numbers.

Output Format

Output the number of winning plans modulo $10^9+7$.

8
1 3 1 5 2 2 2 3
0

40320

24
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
10 15

0

Hint

Constraints:

• For $10\%$ of the testdata, $n \leq 10$.
• For $50\%$ of the testdata, $n \leq 23$.
• For $100\%$ of the testdata, $n \leq 24$, $0 \le m \le 2$, $1 \le a_i, b_i \le 10^9$.

Translated by ChatGPT 5