Zenyk 拥有一个包含 $n$ 个整数的序列 $a_1, \dots, a_n$ 和一个包含 $m$ 个整数的序列 $b_1, \dots, b_m$。两个序列中的元素均为正整数。你构建了一个 $n \times m$ 的矩阵，其中第 $i$ 行第 $j$ 列的元素值为 $a_i$ 和 $b_j$ 的最小公倍数（LCM）。
现在他想知道，有多少对序列 $c$ 和 $d$ 能够产生相同的矩阵。
输入格式
第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)。第二行包含 $n$ 个整数 $a_1, \dots, a_n$。第三行包含 $m$ 个整数 $b_1, \dots, b_m$ ($1 \le a_i, b_j \le 10^9$)。
输出格式
输出满足条件的序列对数，结果对 $1\,000\,000\,007$ ($10^9 + 7$) 取模。
样例
输入格式 1
2 3 2 10 28 3 4
输出格式 1
5