import sys sys.setrecursionlimit(200005) int1 = lambda x: int(x)-1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) def LI1(): return list(map(int1, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def SI(): return sys.stdin.readline().rstrip() # dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] inf = 10**9 # md = 998244353 md = 10**9+7 from functools import lru_cache def factors(a): if a <= 0: return [0] dd0, dd1 = [], [] for d in range(1, a+1): if d*d > a: break if a%d: continue dd0.append(d) dd1.append(a//d) if dd0[-1] == dd1[-1]: dd1.pop() return dd0+dd1[::-1] @lru_cache(None) def cal(a, b): c = aa[-1]-1 if a == b == c: return pow(b[0], m, md)*((m+2)*(m+1)//2)%md if a == c: b, c = c, b if b == c: a, c = c, a if a == b: am = pow(a, m+1, md) return (-c*(m+2)*am%md+a*(m+1)*am%md+pow(c, m+2, md))*pow(a-c, 2*md-4, md)%md return (pow(a, m+2, md)*(b-c)+pow(c, m+1, md)*(a*c-b*c)+pow(b, m+1, md)*(-a*b+b*c))*pow((a-b)*(a-c)*(b-c), md-2, md)%md n, m = LI() m -= 3 aa = [0, 0]+LI() ff = factors(n)[1:-1] ton = [False]*(n+1) ans = 0 for i, f in enumerate(ff): ton[f] = True for g in ff[i+1:]: if g%f: continue ans += cal(aa[f]-1, aa[g]-1) # print(f,g,ans) print(ans) for _ in range(II()): x, y = LI() if y == n: for f in factors(x)[1:-1]: ans = (ans+cal(aa[f]-1, aa[x]))%md ton[x] = True elif ton[y]: ans = (ans+cal(aa[x]-1, aa[y]-1))%md print(ans)