A Math Problem

Limits: 2 sec., 256 MiB

You are given a sequence of \(N\) integers \(A_1, ..., A_N\) and a sequence of \(M\) integers \(B_1, ..., B_M\). Both sequences contain only positive integers. You built a matrix of size \(N \times M\) such that an element at the \(i\)-th row and the \(j\)-th column has value of LCM of values \(A_i\) and \(B_j\).

Now you want to know how many pairs of sequences \(C\) and \(D\) are there that produce the same matrix.

Input

The first line contains two inetegrs \(N\) and \(M\). The second line contains \(N\) integers \(A_1, ..., A_N\). The third line contains \(M\) integers \(B_1, ..., B_N\).

Output

The number of pairs modulo 1000000007 (\(10^9+7\)).

Constraints

\(1 \le N, M \le 100000 (10^5)\),

\(1 \le A_i, B_j \le 1000000000 (10^9)\).

Samples