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 Xth 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 $109+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$ sisN$)$ contains an integer describing A 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$].$Constraints$1<=$ N $<=10^51<=$ A$[$i$]<=10^51<=$ Q$<=10^52<=$ P $<=21<=$ queries$[$i$][$j$]<=10^51$ Import sysdef get Subsequencel ount $($N$,$ A$,$ Q$,$ P$.$ queries$)$:write your code hereMint$($sys$.$stdin.readline$().$strip$())$A$-11$for in range$($N$)$:A$.$append$($int$($sys$.$stdin.readline$().$strip$()))$Qint$($sys$.$stdin.readline$().$strip$())$Pint$($sys$.$stdin.readline$().$strip$())$queries Ifor in range$($Q$)$:queries.append$($list$($map$($lambda x: int$($x$),$ sys$.$stdin.readl