func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MAXN = 2E5 + 10;   const int P = 1E9 + 7;   int n, q;   struct node {     int l, r, id;   } qu[MAXN];   int a[MAXN], pri[1100], cnt;   int num[1000001];   long long ans[MAXN];   long long bin[MAXN];   vector<int> dir[1000001];   vector<int> rec[MAXN];   int pow(int a, int n) {     long long b = a;     long long ret = 1;     while (n) {       if (n & 1) ret = ret * b % P;       b = b * b % P;       n >>= 1;     }     return ret;   }   bool cmp(node n1, node n2) {     if (n1.l != n2.l)       return n1.l < n2.l;     else       return n1.r < n2.r;   }   bool prime(int p) {     for (int i = 0; pri[i] * pri[i] <= p; i++)       if (!(p % pri[i])) return false;     return true;   }   void init() {     pri[cnt = 0] = 2;     for (int i = 3; i < 100000; i++)       if (prime(i)) pri[++cnt] = i;     cnt++;     for (int i = 0; i < MAXN; i++) rec[i].clear();     for (int i = 0; i < MAXN; i++) bin[i] = 1;     for (int i = 0; i < 1000001; i++) dir[i].clear();     memset(num, 0, sizeof(num));   }   int exgcd(long long a, long long b, long long &x, long long &y) {     if (a == 0) {       x = 0;       y = 1;       return b;     } else {       long long tx, ty;       long long d = exgcd(b % a, a, tx, ty);       x = ty - (b / a) * tx;       y = tx;       return d;     }   }   int inverse(int k) {     long long a = k, b = P, x, y;     exgcd(a, b, x, y);     return (x % P + P) % P;   }   int main() {     int temp, l, u, v;     init();     scanf( %d , &n);     for (int i = 1; i <= n; i++) scanf( %d , &a[i]);     scanf( %d , &q);     for (int i = 0; i < q; i++) {       scanf( %d%d , &qu[i].l, &qu[i].r);       qu[i].id = i;     }     sort(qu, qu + q, cmp);     for (int i = 1; i <= n; i++) {       for (int j = 0; pri[j] * pri[j] <= a[i]; j++) {         while (a[i] % pri[j] == 0) {           a[i] /= pri[j];           if (dir[pri[j]].empty())             temp = pri[j] - 1;           else             temp = pri[j];           dir[pri[j]].push_back(i);           rec[i].push_back(pri[j]);           for (int k = i; k <= n; k += k & -k) bin[k] = bin[k] * temp % P;         }       }       if (a[i] != 1) {         if (dir[a[i]].empty())           temp = a[i] - 1;         else           temp = a[i];         dir[a[i]].push_back(i);         rec[i].push_back(a[i]);         for (int k = i; k <= n; k += k & -k) bin[k] = bin[k] * temp % P;       }     }     l = 1;     for (int i = 0; i < q; i++) {       for (; l < qu[i].l; l++) {         for (int j = 0; j < rec[l].size(); j++) {           u = rec[l][j];           if (num[u] < dir[u].size() - 1)             v = dir[u][++num[u]];           else             v = n + 1;           temp = (long long)(u - 1) * inverse(u) % P;           for (int k = v; k <= n; k += k & -k) bin[k] = bin[k] * temp % P;         }       }       temp = qu[i].id;       ans[temp] = 1;       for (int k = qu[i].l - 1; k > 0; k -= k & -k)         ans[temp] = ans[temp] * bin[k] % P;       ans[temp] = inverse(ans[temp]);       for (int k = qu[i].r; k > 0; k -= k & -k) {         ans[temp] = ans[temp] * bin[k] % P;       }     }     for (int i = 0; i < q; i++) printf( %lld n , ans[i]);   }   