Description

There is a sequence of length $n$, and xht37 now wants to maintain it using block decomposition.

PinkRabbit requires that he may only divide the sequence into blocks whose lengths come from $PR$ allowed lengths.

NaCly_Fish requires that he may only divide the sequence into blocks whose lengths come from $NF$ allowed lengths.

The same person may request the same block length multiple times.

xht37 wants to satisfy both PinkRabbit and NaCly_Fish, so he has to use block lengths that are allowed by both of them.

xht37 wants to know how many different block decomposition schemes there are. Output the answer modulo $10 ^ 9 + 7$.

Input Format

The first line contains a positive integer $n$, which is the length of the sequence.

The second line contains a positive integer $PR$, which is the number of allowed block lengths requested by PinkRabbit.

The third line contains $PR$ positive integers, representing the $PR$ block lengths requested by PinkRabbit.

The fourth line contains a positive integer $NF$, which is the number of allowed block lengths requested by NaCly_Fish.

The fifth line contains $NF$ positive integers, representing the $NF$ block lengths requested by NaCly_Fish.

Output Format

Output one line with one integer, which is the number of different block decomposition schemes modulo $10 ^ 9 + 7$.

4
3
1 2 3
3
1 2 4

5

19260817
7
8 9 6 3 7 2 1
7
4 5 2 9 7 8 3

859254329

Hint

[Sample $1$ Explanation]

The block lengths allowed by both PinkRabbit and NaCly_Fish are $\{1,2\}$.

For a sequence of length $4$, the schemes that divide it into blocks with lengths in $\{1,2\}$ are:

• $1\ 1\ 1\ 1$
• $1\ 1\ 2$
• $1\ 2\ 1$
• $2\ 1\ 1$
• $2\ 2$

There are $5$ schemes in total.

[Constraints]

Let the maximum block length be $x$.

For $60 \%$ of the testdata, $1 \le n \le 10 ^ 6$, $1 \le PR,NF,x \le 10$, and it is guaranteed that the same person will not request the same block length multiple times.

For $100 \%$ of the testdata, $1 \le n \le 10 ^ {18}$, $1 \le PR,NF,x \le 100$.

Translated by ChatGPT 5