小红拿到了一个数组，她有以下一种操作：

将[l,r]区间所有数变成该区间所有数的lcm，并输出这个lcm。

区间lcm指区间内所有数的最小公倍数。

一共次操作。

输入描述:

第一行输入两个正整数，代表数组长度和查询次数。
第二行输入个正整数，代表小红拿到的数组。
接下来的行，每行输入两个正整数，用空格隔开。




保证数据随机生成。

输出描述:

对于每一次操作，输出操作后区间[l,r]的lcm对1e9+7取模的值。

5 2
4 6 9 10 16
1 3
3 5

36
720

备注:

使用如下的python程序生成数据：
import random
def createData():
    n = random.randint(1, 20000)
    q = random.randint(1, 20000)
    print(n, q)
    for i in range(n):
        print(random.randint(1, 20000), end=" ")
    print()
    for i in range(q):
        l = random.randint(1, n)
        r = random.randint(1, n)
        if l > r:
            l, r = r, l
        print(l, r)