A. LIS and GCD
time limit per test
15 s
memory limit per test
1024 MB
input
standard input
output
standard output

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.

Input

The first input line contains one integer number n. The second line contains n integer numbers ai. The third line contains n integer numbers bi.

1 ≤ n ≤ 105
1 ≤ ai ≤ 109
1 ≤ bi ≤ 106
Output

Display the answer modulo 109 + 7.

Examples
Input
2
1 2
1 2
Output
4
Input
2
2 1
1 2
Output
3
Input
4
2 3 1 4
2 3 6 9
Output
29
Note

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.