수학 문제

시간 제한1초메모리 제한512 MB

요약

두 수열 a와 b가 주어질 때, lcm(a_i, b_j)로 만든 행렬과 같은 행렬을 만드는 수열 쌍 (c, d)의 개수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Zenyk에게 정수 수열 $a_1, \ldots, a_n$ 과 정수 수열 $b_1, \ldots, b_m$ 이 주어진다. 두 수열은 모두 양의 정수로만 이루어져 있다. 당신은 $n \times m$ 크기의 행렬을 만들었다. 이 행렬의 $i$ 행 $j$ 열 값은 $a_i$ 와 $b_j$ 의 최소공배수(LCM)이다.

이제 Zenyk은 같은 행렬을 만드는 수열 쌍 $c$ 와 $d$ 가 몇 쌍 있는지 알고 싶어 한다.

입력

첫 줄에 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \le n, m \le 10^5$ ). 둘째 줄에는 $n$ 개의 정수 $a_1, \ldots, a_n$ 이, 셋째 줄에는 $m$ 개의 정수 $b_1, \ldots, b_m$ 이 주어진다 ( $1 \le a_i, b_j \le 10^9$ ).

출력

쌍의 개수를 $10^9 + 7$ 로 나눈 나머지를 출력한다.

예제1

예제 1
입력
```
2 3
2 10
28 3 4
```
예상 출력
```
5
```