【XR-1】分块

内存限制：256 MB 时间限制：1000 ms

xht37 喜欢分块，以至于对一道不需要分块的题也要分块做。

有一个长度为 $n$ 的序列，xht37 现在想分块维护它。

PinkRabbit 要求他只准将序列分成 $PR$ 种长度的块。

NaCly_Fish 要求他只准将序列分成 $NF$ 种长度的块。

同一个人可能会要求 xht37 多次相同的块长。

xht37 想同时满足 PinkRabbit 和 NaCly_Fish 要求，只好使用两个人都允许的长度分块。

xht37 想知道，有多少种不同的分块方案，答案对 $10 ^ 9 + 7$取模。

第一行一个正整数 $n$，表示序列的长度。

第二行一个正整数 $PR$，表示 PinkRabbit 要求的分块长度的种类数。

第三行 $PR$ 个正整数，表示 PinkRabbit 要求的 $PR$ 种分块长度。

第四行一个正整数 $NF$，表示 NaCly_Fish 要求的分块长度的种类数。

第五行 $NF$ 个正整数，表示 NaCly_Fish 要求的 $NF$ 种分块长度。

输出一行一个整数，表示不同分块方案的种类数对 $10 ^ 9 + 7$ 取模的值。

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

859254329

【数据规模与约定】

设最大块长为 $x$。

对于 $60 \%$ 的数据，$1 \le n \le 10 ^ 6$，$1 \le PR,NF,x \le 10$，保证同一个人不会要求多次相同的块长。

对于 $100 \%$ 的数据，$1 \le n \le 10 ^ {18}$，$1 \le PR,NF,x \le 100$。

C1561 【XR-1】分块