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
Input (stdin) | Output (stdout) |
---|---|
2 3 2 10 28 3 4 | 5 |
Source: Змагання Шефа 10
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|