401902: GYM100570 A LCM Query

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. LCM Querytime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

De Prezer loves lcm (Least Common Multiple).Ha has got a sequence a1, a2, ..., an but doesn't know how to calculate lcm of two numbers.

De Prezer also loves query.So he asks you to answer to m queries on this sequence.

In each query, he gives you number x and you should print the following number :

lcm(ai, ai + 1, ..., ai + x - 1)

Answer can be very large, so print it modulo 109 + 7 .

Input

The first line of input consists of 2 integers n and m.

The second line of input contains n space separated integers a1, a2, ..., an.

The next m lines, each line contains an integer x.

1 ≤ n ≤ 2 * 104

1 ≤ m ≤ 106

1 ≤ ai ≤ 60 (For each 1 ≤ i ≤ n)

1 ≤ x ≤ n

Output

Print m lines, each answer to one query.

ExamplesInput
5 5
1 2 3 4 5
1
2
3
4
5
Output
1
2
6
12
60
Input
5 5
2 3 1 4 5
1
2
3
4
5
Output
1
3
6
12
60

加入题单

上一题 下一题 算法标签: