|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||4||4||4||100.000%|
Zenyk is given a sequence of n integers a1, . . . , an and a sequence of m integers b1, . . . , bm. Both sequences contain only positive integers. You built a matrix of size n × m such that an element at the i-th row and the j-th column has value of LCM (least common multiple) of values ai and bj.
Now he wants to know how many pairs of sequences c and d are there that produce the same matrix.
The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains n integers a1, . . . , an. The third line contains m integers b1, . . . , bm (1 ≤ ai, bj ≤ 109).
The number of pairs modulo 1 000 000 007 (109 + 7).
2 3 2 10 28 3 4