A Math Problem
시간 제한1초메모리 제한512 MB
주어진 두 수열 (a, b)로 만든 n 곱하기 m LCM 행렬과 같은 행렬을 만드는 양의 정수 수열 쌍 (c, d)의 개수를 1e9+7로 나눈 나머지로 구한다.
문제
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).