18731번 - A Math Problem 다국어

문제

Zenyk is given a sequence of n integers a₁, . . . , a_n and a sequence of m integers b₁, . . . , b_m. 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 a_i and b_j.

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 ≤ 10⁵). The second line contains n integers a₁, . . . , a_n. The third line contains m integers b₁, . . . , b_m (1 ≤ a_i, b_j ≤ 10⁹).

출력

The number of pairs modulo 1 000 000 007 (10⁹ + 7).

제한

힌트