A Math Problem

Zenyk is given a sequence of $n$ integers $a_1, \ldots, a_n$ and a sequence of $m$ integers $b_1, \ldots, b_m$. Both sequences contain only positive integers. You built a matrix of size $n \times m$ such that the element in the $i$-th row and the $j$-th column is the LCM (least common multiple) of $a_i$ and $b_j$.

Now he wants to know how many pairs of sequences $c$ and $d$ produce the same matrix.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$). The second line contains $n$ integers $a_1, \ldots, a_n$. The third line contains $m$ integers $b_1, \ldots, b_m$ ($1 \le a_i, b_j \le 10^9$).

Print the number of pairs modulo $10^9 + 7$.