You are given an array A of length N.
A subsequence is said to be great if the GCD of the elements of the subsequence is greater than 1. An empty subsequence is not a great subsequence.
You are given Q queries and in each query you are given two integers X and Y (1 <= X <= N, 1 <= Y <= 10^5). You need to replace the X^th element in A with Y. In other words, set A[X] = Y. Let the answer to each query be the number of great subsequences.
Let's define an array S containing the answer to each query.
Find the sum of S. Since the answer can be large, return it modulo 10^9 + 7.
Input Format
The first line contains an integer, N, denoting the number of elements in A.
Each line i of the N subsequent lines (where 1 <= i <= N) contains an integer describing A[i].
The next line contains an integer, Q, denoting the number of rows in queries.
The next line contains an integer, P, denoting the number of columns in queries.
Each line i of the Q subsequent lines (where 1 <= i <= Q) contains P space separated integers each describing the row queries[i].
Example 1:
Input: A = [1, 2], queries = [[1, 2]]
Output: 3
Explanation:Given N=2, A=[1,2], Q=1, P=2, queries=[(1,2)]
After the first query, the subsequences are [2, 2], [2] and [2]. All of these GCD is more than 1. So, answer is 3.
Example 2:
Input: A = [1, 2, 3], queries = [[1, 3], [2, 3]]
Output: 11
Explanation:Given N=3, A=[1,2,3], Q=2, P=2, queries=[(1,3), (2,3)]
After query 1, A become [3,2,3], then good subsequences are [2],[3],[3],[3,3].
After query 2, A become [3,3,3], then good subsequences are [3],[3],[3],[3,3],[3,3],[3,3],[3,3,3]
So, answer is 4+7=11.
Example 3:
Input: A = [2, 2, 2, 2, 2], queries = [[1, 1], [2, 1]]
Output: 22
Explanation:Given N=5, A=[2,2,2,2,2], Q=2, P=2, queries=[(1,1), (2,1)]
After query 1, A = [1,2,2,2,2], then total number of good subsequences is 15.
After query 2, total number of good sequence is 7.
Hence, the answer is 15+7=22.
1 <= N <= 10^5
1 <= A[i] <= 10^5
1 <= Q <= 10^5
2 <= P <= 2
1 <= queries[i][j] <= 10^5
input:
output: