시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 51 | 17 | 17 | 33.333% |
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
5