#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

// #define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;
const ll mod = 1e9 + 7;

struct query {
    int l, r;
    int i;
};

int n, k;
vector<int> a;
int q;
vector<query> t;
vector<ll> rs;
vector<vector<ll>> b;

void solve(int tl, int tr, vector<query> &t) {
    if (t.empty()) {
        return;
    }
    if (tl == tr) {
        for (auto [l, r, i] : t) {
            rs[i] = 2;
        }
        return;
    }
    bool interesting_asks = false;
    int tm = (tl + tr) / 2;
    for (auto [l, r, i] : t) {
        if (r <= tm) {
        } else if (tm + 1 <= l) {
        } else {
            interesting_asks = true;
        }
    }
    if (interesting_asks) {
        vector<vector<ll>> dp(k, vector<ll>(k, 0));
        vector<ll> aboba(k);
        for (int i = tm; i >= tl; i -= 1) {
            ll f = a[i];
            for (int x = f; x < k; x += 1) {
                for (int y = f; y <= x; y += 1) {
                    dp[x][f] += dp[x][y];
                }
                dp[x][f] %= mod;
            }
            dp[f][f] = (dp[f][f] + 1) % mod;
            for (ll x = 0; x < k; x += 1) {
                aboba[x] = 0;
                for (ll y = 0; y < k; y += 1) {
                    aboba[x] += dp[x][y];
                }
                aboba[x] %= mod;
            }
            b[i] = aboba;
        }
        dp.assign(k, vector<ll>(k));
        for (int i = tm + 1; i <= tr; i += 1) {
            ll f = a[i];
            for (int x = f; x >= 0; x -= 1) {
                for (int y = f; y >= x; y -= 1) {
                    dp[x][f] = (dp[x][f] + dp[x][y]) % mod;
                }
            }
            dp[f][f] = (dp[f][f] + 1) % mod;
            for (ll x = 0; x < k; x += 1) {
                aboba[x] = 0;
                for (ll y = 0; y < k; y += 1) {
                    aboba[x] += dp[x][y];
                }
                aboba[x] %= mod;
            }
            b[i] = aboba;
        }
    }
    vector<query> tlft, trght;
    for (auto [l, r, i] : t) {
        if (r <= tm) {
            tlft.push_back(query{l, r, i});
        } else if (tm + 1 <= l) {
            trght.push_back(query{l, r, i});
        } else {
            ll ans = 1;
            ll sm = 0;
            for (int j = 0; j < k; j += 1) {
                sm = (sm + b[l][j]) % mod;
                ans = (ans + sm * b[r][j] + b[l][j] + b[r][j]) % mod;
            }
            rs[i] = ans;
        }
    }
    solve(tl, tm, tlft);
    solve(tm + 1, tr, trght);
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        cin >> a[i];
        --a[i];
    }
    cin >> q;
    t.resize(q);
    for (int i = 0; i < q; i += 1) {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        t[i] = query{l, r, i};
    }
    rs.assign(q, 0);
    b.resize(n);
    solve(0, n - 1, t);
    for (auto x : rs) {
        cout << x << "\n";
    }
    return 0;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:6:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~