Background

yyy has a special affection for certain numbers, which he calls "lucky numbers." However, due to his mischievous nature, he refers to the numbers he dislikes as "unlucky numbers."

Problem Description

A group of friends are playing a game with yyy.

Each round, they give yyy \( n \) cards, each with a number on it. All these numbers are "lucky numbers," and the number on the \( i \)-th card is \( a_i \).

Each time, yyy can choose to move forward \( a_i \) steps and discard the \( i \)-th card. He wins when he has no cards left.

However, friends have set traps at positions of "unlucky numbers." If yyy stops at such a position, he loses. Note: Even if he reaches the end, but the position is an unlucky number, he still loses.

Now, some friends are wondering: What is the probability of yyy winning?

They think this is a good question and immediately ask yyy to write a program: "Computers are fast! The factorial of 24 is only \( 620,448,401,733,239,439,360,000 \). yyy, quickly write a program to calculate it."

yyy is speechless and says he doesn't want to calculate the probability, but rather the number of winning ways, modulo \( 10^9+7 \).

Everyone else can't write a program, so they compromise.

But now yyy is troubled, as \( 24! \) is too large and would take a long time to compute.

He is severely short on time! He needs your help!

A number might be both a lucky number and an unlucky number.

Input Format

The first line contains an integer \( n \).

The next line contains \( n \) integers, where the \( i \)-th integer represents the number \( a_i \) on the \( i \)-th card.

The third line contains an integer \( m \), indicating the number of unlucky numbers (at most 2).

If \( m > 0 \), the fourth line contains \( m \) numbers \( b_i \), representing all the unlucky numbers.

Output Format

Output the number of winning ways modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

8
1 3 1 5 2 2 2 3
0

Sample Output #1

40320

Sample Input #2

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

Sample Output #2

0

Notes

• \( 10\% \) of the test cases have \( n \leq 10 \);
• \( 50\% \) of the test cases have \( n \leq 23 \);
• \( 100\% \) of the test cases have \( n \leq 24 \), \( 0 \leq m \leq 2 \), \( 1 \leq a_i, b_i \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分