#include <bits/stdc++.h>
#define ll long long
#define vll vector
#define mat vector
using namespace std;
ll gcd(ll a, ll b) {
if(b == 0) {
return a;
} else {
return gcd(b, a%b);
}
}
const ll MOD = 1e9+7;
const ll N = 1e5+5;
ll n;
ll segmentTree[2*N];
void build() {
for(int i = n-1; i > 0; --i) {
segmentTree[i] = gcd(segmentTree[i<<1], segmentTree[i<<1|1]);
}
}
ll query(ll l, ll r) {
ll res = segmentTree[l+n];
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l&1) {
res = gcd(res, segmentTree[l++]);
}
if(r&1) {
res = gcd(res, segmentTree[–r]);
}
}
return res;
}
mat multiply(mat A, mat B) {
mat C(3, vll(3, 0));
for(int i = 1; i < 3; ++i) {
for(int j = 1; j < 3; ++j) {
for(int k = 1; k < 3; ++k) {
C[i][j] += (A[i][k] * B[k][j])%MOD;
}
}
}
return C;
}
mat power(mat A, ll p) {
if(p == 1) {
return A;
}
if(p&1) {
return multiply(A, power(A, p-1));
} else {
mat X = power(A, p >> 1);
return multiply(X, X);
}
}
ll compute(ll n) {
// Initial Vector
vll F1(3, 0);
F1[1] = F1[2] = 1;
// Transformation Matrix
mat T(3, vll(3, 0));
T[1][1] = 0;
T[1][2] = 1;
T[2][1] = 1;
T[2][2] = 1;
T = power(T, n-1);
ll res = 0;
for(int i = 1; i < 3; i++) {
res = (res + (T[1][i] * F1[i]) % MOD) % MOD;
}
return res;
}
int main() {
ll q;
cin >> n >> q;
for(int i = 0; i < n; ++i) {
cin >> segmentTree[i+n];
}
build();
while(q–) {
ll l, r;
cin >> l >> r;
l–;
r–;
cout << compute(query(l, r+1))%MOD << endl;
}
return 0;
}