P2396 yyy loves Maths VII

yyy has a special affection for certain numbers, which he calls "lucky numbers"; however, because he has tempted fate too many times, he calls the numbers he dislikes "unlucky numbers".

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.

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 the number of winning plans modulo $10^9+7$.

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