403539: GYM101192 A LIS and GCD

You are given two arrays a and b. Each array has n integer numbers. You need to compute the sum of GCDs of all subsequences of array b such that the corresponding subsequences of array a are increasing.

The first input line contains one integer number n. The second line contains n integer numbers a_i. The third line contains n integer numbers b_i.

Display the answer modulo 10⁹ + 7.

2
1 2
1 2

4

2
2 1
1 2

3

4
2 3 1 4
2 3 6 9

29

Third example: Here are examples of increasing subsequences from a and the corresponding GCD values: {2}->2, {3}->3, {1}->6, {4}-> 9, {2,3}->1, {2,4}->1, {3,4}->3, {1,4}->3, {2,3,4}->1.