Background

xht37 loves block division so much that he even tries to divide a sequence that doesn't require block division into blocks.

Problem Description

There is a sequence of length \( n \), and xht37 wants to maintain it using block division.

PinkRabbit requires him to only divide the sequence into \( PR \) types of block lengths.

NaCly_Fish requires him to only divide the sequence into \( NF \) types of block lengths.

The same person may require xht37 to use the same block length multiple times.

xht37 wants to satisfy both PinkRabbit and NaCly_Fish, so he has to use the block lengths allowed by both.

xht37 wants to know how many different block division schemes there are, with the answer modulo \( 10^9 + 7 \).

Input Format

The first line contains a positive integer \( n \), representing the length of the sequence.

The second line contains a positive integer \( PR \), representing the number of types of block lengths required by PinkRabbit.

The third line contains \( PR \) positive integers, representing the \( PR \) types of block lengths required by PinkRabbit.

The fourth line contains a positive integer \( NF \), representing the number of types of block lengths required by NaCly_Fish.

The fifth line contains \( NF \) positive integers, representing the \( NF \) types of block lengths required by NaCly_Fish.

Output Format

Output a single integer, representing the number of different block division schemes modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

4
3
1 2 3
3
1 2 4

Sample Output #1

5

Sample Input #2

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

Sample Output #2

859254329

Notes

Sample 1 Explanation

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

For a sequence of length 4, the block division schemes with block lengths \(\{1, 2\}\) are:

• \(1 \ 1 \ 1 \ 1\)
• \(1 \ 1 \ 2\)
• \(1 \ 2 \ 1\)
• \(2 \ 1 \ 1\)
• \(2 \ 2\)

Totaling 5 schemes.

Data Constraints

Let the maximum block length be \( x \).

For 60% of the data, \( 1 \le n \le 10^6 \), \( 1 \le PR, NF, x \le 10 \), and the same person will not require the same block length multiple times.

For 100% of the data, \( 1 \le n \le 10^{18} \), \( 1 \le PR, NF, x \le 100 \).

见题面 Input 部分

见题面 Output 部分