A. LCM Query
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Examples
Input
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