「CZYZOI 2017.04.23 B」 req

内存限制: 256 MiB 时间限制: 2000 ms
标准输入输出

题目描述

众所周知 ϕ(n)\phi (n) 表示比 nn 小的与 nn 互质的数的个数。

MM 最近在《蒜法导论》上看到了这样一道题:给出 nn 个正整数 v[1],v[2]....v[n]v[1],v[2]....v[n]qq 次询问,每次询问一个区间 [l,r][l,r]

x=v[l]v[l+1]...v[r]x=v[l]*v[l+1]*...*v[r] ,要求求出 ϕ(x)\phi (x)109+710^9+7 取模的余数。

大M对此十分感兴趣并找到了你,请你解决这个问题。

输入格式

第一行仅一个数n表示给出的数字的个数。

第二行 nn 个数即所给出的数字。

第三行一个数 qq 表示询问的个数。

接下来 qq 行每行 22 个数 l,rl,r 表示询问的区间 [l,r][l,r]

输出格式

输出 qq 个数表示每个询问的答案

样例

输入样例1

10
1 2 3 4 5 6 7 8 9 10
7
1 1
3 8
5 6
4 8
8 10
7 9
7 10

输出样例1

1
4608
8
1536
192
144
1152

输入样例2

7
24 63 13 52 6 10 1
6
3 5
4 7
1 7
2 4
3 6
2 6

输出样例2

1248
768
12939264
11232
9984
539136

数据范围与提示

对于 20%20\% 的数据,n100,q100n\le100,q\le100

对于 100%100\% 的数据,n100000,q100000,1v[i]106n\le100000,q\le100000,1\le v[i]\le10^6