P5343 [XR-1] Block Decomposition

xht37 likes block decomposition so much that he even uses it to solve a problem that **does not need block decomposition**.

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$.

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 one line with one integer, which is the number of different block decomposition schemes modulo $10 ^ 9 + 7$.

[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