시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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).

예제 입력 1

2 3
2 10
28 3 4

예제 출력 1

5