You've got an array *a*, consisting of *n* integers. The array elements are indexed from 1 to *n*. Let's determine a two step operation like that:
 1.  First we build by the array *a* an array *s* of partial sums, consisting of *n* elements. Element number *i* (1 ≤ *i* ≤ *n*) of array *s* equals <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/cdc22b6f0de971f5a4a64b6f9e22d76a719ec5b7.png" style="max-width: 100.0%;max-height: 100.0%;"/>. The operation *x* *mod* *y* means that we take the remainder of the division of number *x* by number *y*. 1.  Then we write the contents of the array *s* to the array *a*. Element number *i* (1 ≤ *i* ≤ *n*) of the array *s* becomes the *i*-th element of the array *a* (*a*<sub class="lower-index">*i*</sub> = *s*<sub class="lower-index">*i*</sub>). 
You task is to find array *a* after exactly *k* described operations are applied.
The first line contains two space-separated integers *n* and *k* (1 ≤ *n* ≤ 2000, 0 ≤ *k* ≤ 10<sup class="upper-index">9</sup>). The next line contains *n* space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> — elements of the array *a* (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
#-----------------------------------------Multiset------------------------------------------------------------------


class Multiset(object):
  def __init__(self, powersSize):
    self.tuples = {}
    self.powersSize = powersSize
    

  def add(self, item, idx):
    if not item in self.tuples: #no esta el factor primo
        tuple = []
        tuple.append(1)
        powers=[]
        for i in range(self.powersSize):
            powers.append(0)
        tuple.append(powers)
        tuple[1][idx] = 1
        self.tuples[item] = tuple
    else:
        if self.tuples[item][1][idx] == 0:
            self.tuples[item][0]+=1
        self.tuples[item][1][idx]+=1

#--------------------------------------------------------------------------------------------------------

primesDescomposition={}   

def fillPrimeFactors(item, index, primeFactors, length):
    d = 1
    n = item
    gcd = 1
    prevOc=0
    factors=[]
    
    while not n in primesDescomposition and n > 1:
        if d == 1:
            d+= 1 
        if n % d == 0:
            factors.append(d)
            if d in primeFactors.tuples and primeFactors.tuples[d][0]== length:
                prevOc= min(primeFactors.tuples[d][1])  
            primeFactors.add(d, index)
            current = primeFactors.tuples[d]           
            if current[0] == length:
                power = min(current[1])
                gcd *= d ** (power-prevOc)
            n = n/d
        else:
            d+= 1
            prevOc=0
    
    if not item in primesDescomposition:
        if n in primesDescomposition:
            factors= factors + primesDescomposition[n]
        primesDescomposition[item]= factors
        
    if  n!=1:
        for i in range(len(primesDescomposition[n])):
            d=primesDescomposition[n][i]
            prevOc=0
            if d in primeFactors.tuples and primeFactors.tuples[d][0]== length:
                prevOc= min(primeFactors.tuples[d][1])  
            primeFactors.add(d, index)
            current = primeFactors.tuples[d]           
            if current[0] == length:
                power = min(current[1])
                gcd *= d ** (power-prevOc)
    
    return primeFactors, gcd

# """ def fillPrimeFactors(item, index, primeFactors, length):
#     d = 1
#     n = item
#     gcd = 1
#     prevOc=0
#     while d * d <= n:
#         if d == 1:
#             d+= 1 
#         while n > 1: 
#             while n % d == 0:    
#                 if  d in primeFactors.tuples and primeFactors.tuples[d][0]== length:
#                     prevOc= min(primeFactors.tuples[d][1])  
#                 primeFactors.add(d, index)
#                 current = primeFactors.tuples[d]           
#                 if current[0] == length:
#                     power = min(current[1])
#                     gcd *= d ** (power-prevOc)
#                 n = n/d
#             d+= 1
#             prevOc=0
#     return primeFactors, gcd """
    
    
def GCD_of_an_array(a, queries):
    
    primeFactors = Multiset(len(a))
    result = []
    
    for i in range(len(a)):
        primeFactors, mcd = fillPrimeFactors(a[i], i, primeFactors, len(a))
    
    for i in range (len(queries)):
        item1 = queries[i].__getitem__(0) - 1
        item2 = queries[i].__getitem__(1)
        a[item1] = a[item1] * item2
        primeFactors, aux = fillPrimeFactors(item2, item1, primeFactors,  len(a))
        mcd *= aux 
        result.append(int(mcd % (10 ** 9 +7)))
    
    return result


#-------------------------------------------------------- Lectura de consola------------------------------------------------------------
sizes = input()
length_a, length_queries = sizes.split()

aux = input().split()
a = []
for i in range(int(length_a)):
    a.append(int(aux[i]))

queries = []
for i in range(int(length_queries)):
    line = input().split()
    queries.append((int(line[0]), int(line[1])))

ans= GCD_of_an_array(a,queries)

for i in range(len(ans)):
    print(ans[i])

#----------------------------------------------------------------------------------------------------------------------------------------





