Даны два массива целых чисел a и b длины n каждый. Необходимо посчитать сумму НОД-ов подпоследовательностей массива b таких, что соответствующая подпоследовательность массива a является возрастающей.
Первая строка содержит одно целое число n. Вторая строка содержит n целых чисел ai. Третья строка содержит n целых чисел bi.
Выведите ответ на задачу по модулю 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.
