Математична колегія
Обмеження: 2 сек., 256 МіБ
Мало кому відомо, що при нашому парламенті діє математична колегія. Дивовижним є те, що складається вона виключно з депутатів Верховної Ради. Хто б подумав?!
Під час цьогорічного скликання математична колегія займається проблемами найменшого спільного кратного. Члени колегії мають стовпець \(a\) з \(n\) натуральних чисел \(a_i\) та рядок \(b\) з \(m\) натуральних чисел \(b_j\). За декілька днів вони зуміли побудувати матрицю розміру \(n \times m\), яка на перетині \(i\)-го рядка та \(j\)-го стовпця містить найменше спільне кратне чисел \(a_i\) та \(b_j\).
Наразі талановиті депутати працюють над обрахунком кількості таких пар (\(c\), \(d\)), що дають таку ж матрицю. Зауважте, що стовпець \(c\) та рядок \(d\) мають також містити тільки натуральні числа. Допоможіть бідолашним депутатонауковцям.
Вхідні дані
У першому рядку задано два натуральних числа \(n\) та \(m\) — розмірність стовпця \(a\) і рядка \(b\) відповідно.
У другому рядку задано \(n\) натуральних чисел \(a_i\) — елементи стовпця \(a\).
У третьому рядку задано \(m\) натуральних чисел \(b_i\) — елементи рядка \(b\).
Вихідні дані
У єдиному рядку виведіть одне ціле число — остача від ділення кількості пар на просте число \(10^9+7\).
Обмеження
\(1 \le n, m \le 10^5\),
\(1 \le a_i, b_j \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 3 2 10 28 3 4 | 5 |
Примітки
Таку матрицю можна отримати за допомогою таких пар:
([2 10], [28 3 4])
([2 10], [28 6 4])
([1 10], [28 6 4])
([2 5], [28 6 4])
([1 5], [28 6 4])
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|