A. LIS и GCD
ограничение по времени на тест
15 с
ограничение по памяти на тест
1024 МБ
ввод
стандартный ввод
вывод
стандартный вывод

Даны два массива целых чисел a и b длины n каждый. Необходимо посчитать сумму НОД-ов подпоследовательностей массива b таких, что соответствующая подпоследовательность массива a является возрастающей.

Входные данные

Первая строка содержит одно целое число n. Вторая строка содержит n целых чисел ai. Третья строка содержит n целых чисел bi.

1 ≤ n ≤ 105
1 ≤ ai ≤ 109
1 ≤ bi ≤ 106
Выходные данные

Выведите ответ на задачу по модулю 109 + 7.

Примеры
Входные данные
2
1 2
1 2
Выходные данные
4
Входные данные
2
2 1
1 2
Выходные данные
3
Входные данные
4
2 3 1 4
2 3 6 9
Выходные данные
29
Примечание

Третий пример. Возможны следующие возрастающие подпоследовательности в a и соответствующие им НОД-ы:

{2}->2, {3}->3, {1}->6, {4}-> 9, {2,3}->1, {2,4}->1, {3,4}->3, {1,4}->3, {2,3,4}->1.