#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

const int mod = 1e9 + 7;

struct fenwick {
    int n;
    vector<int> t;
    fenwick() = default;
    fenwick(int n_) {
        n = n_;
        t.assign(n + 1, 0);
    }

    void clear() {
        t.assign(n + 1, 0);
    }
 
    void upd(int p, int vl) {
        for (; p <= n; p = (p | (p + 1))) {
            t[p] += vl;
            if (t[p] >= mod) t[p] -= mod;
        }
    }
 
    int get(int p) {
        int sm = 0;
        for (; p > 0; p = (p & (p + 1)) - 1) {
            sm += t[p];
            if (sm >= mod) sm -= mod;
        }
        return sm;
    }
};

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int q; cin >> q;
    vector<vector<pair<int, int>>> qrs(n);
    vector<int> answ(q);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        l--; r--;
        qrs[l].pb({r, i});
    }
    for (int i = 0; i < n; i++) sort(all(qrs[i]));
    vector<vector<int>> dp(n, vector<int>(k + 1));
    vector<fenwick> fw_right(k + 1), fw_left(k + 1);
    for (int i = 1; i <= k; i++) {
        fw_right[i] = fenwick(k + 2);
        fw_left[i] = fenwick(k + 2);
    }
    auto solve = [&](int l, int r, auto&&self) -> void {
        if (l + 1 == r) {
            for (auto &u : qrs[l]) {
                answ[u.second] = 2;
            }
            qrs[l].clear();
            return;
        }
        int tm = (l + r) / 2;
        for (int i = 1; i <= k; i++) {
            fw_right[i].clear(); fw_left[i].clear();
        }
        for (int i = tm; i < r; i++) {
            for (int j = 1; j <= a[i]; j++) {
                fw_right[j].upd(a[i], fw_right[j].get(a[i]));
                if (j == a[i]) fw_right[j].upd(a[i], 1);
            }
            for (int j = 1; j <= k; j++) dp[i][j] = fw_right[j].get(k);
        }
        for (int i = tm - 1; i >= l; i--) {
            for (int j = a[i]; j <= k; j++) {
                fw_left[j].upd(a[i], (fw_left[j].get(k) - fw_left[j].get(a[i] - 1) + mod) % mod);
                if (j == a[i]) fw_left[j].upd(a[i], 1);
            }
            for (int j = 1; j <= k; j++) dp[i][j] = fw_left[j].get(k);
        }
        for (int i = l; i < tm; i++) {
            while (!qrs[i].empty() && qrs[i].back().first >= tm) {
                int rg = qrs[i].back().first;
                int sm = 0, ans = 1;
                for (int j = 1; j <= k; j++) {
                    ans += dp[rg][j] + dp[i][j];
                    ans %= mod;
                    sm += dp[i][j];
                    if (sm >= mod) sm -= mod;
                    ans += dp[rg][j] * 1ll * sm;
                    ans %= mod;
                }
                answ[qrs[i].back().second] = ans;
                qrs[i].pop_back();
            }
        }

        self(l, tm, self);
        self(tm, r, self);
    };
    solve(0, n, solve);
    for (auto &u : answ) cout << u << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}