【XR-1】分块

题目背景

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$ 取模的值。

输入输出样例

输入样例 #1

4
3
1 2 3
3
1 2 4

输出样例 #1

5

输入样例 #2

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

输出样例 #2

859254329

说明

【样例 $1$ 说明】 PinkRabbit 和 NaCly_Fish 都允许的块长为 $\{1,2\}$。 长度为 $4$ 的序列分块,每块长度为 $\{1,2\}$ 的方案有: - $1\ 1\ 1\ 1$ - $1\ 1\ 2$ - $1\ 2\ 1$ - $2\ 1\ 1$ - $2\ 2$ 共 $5$ 种。 【数据规模与约定】 设最大块长为 $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$。