#include <bits/stdc++.h> #define ll long long #define gmax(x, y) x = max(x, y) #define gmin(x, y) x = min(x, y) #define F first #define S second #define P pair #define FOR(i, a, b) for (int i = a; i <= b; i++) #define rep(i, a, b) for (int i = a; i < b; i++) #define V vector #define RE return #define ALL(a) a.begin(), a.end() #define MP make_pair #define PB emplace_back #define PF push_front #define FILL(a, b) memset(a, b, sizeof(a)) #define lwb lower_bound #define upb upper_bound #define lc (x << 1) #define rc ((x << 1) | 1) #define sz(x) ((int)x.size()) #define pc putchar using namespace std; const int mod = 1e9 + 7, B = 3e5; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } int POW(int x, int y) { int re = 1; while (y) { if (y & 1) re = 1ll * re * x % mod; x = 1ll * x * x % mod; y /= 2; } RE re; } int pre[300005], suf[300005], m, k, n; struct bit { int s[300005]; void init(int n) { FOR(i, 1, n) s[i] = 0; } void update(int x, int y) { while (x <= n) { s[x] += y; x += x & -x; } } int get(int x) { int re = 0; while (x) { re += s[x]; x -= x & -x; } RE re; } } T; int num[300005]; struct seg { int tag[1 << 20], sum[1 << 20]; void build(int x, int l, int r) { tag[x] = 1; if (l == r) { sum[x] = num[l]; RE; } int mid = (l + r) >> 1; build(lc, l, mid); build(rc, mid + 1, r); sum[x] = sum[lc]; add(sum[x], sum[rc]); } void pd(int x, int y) { tag[x] = 1ll * tag[x] * y % mod; sum[x] = 1ll * sum[x] * y % mod; } void pushdown(int x) { if (tag[x] != 1) { pd(lc, tag[x]); pd(rc, tag[x]); } tag[x] = 1; } void ins(int x, int l, int r, int it, int val) { if (l == r) { add(sum[x], val); RE; } int mid = (l + r) >> 1; pushdown(x); if (mid >= it) ins(lc, l, mid, it, val); else ins(rc, mid + 1, r, it, val); sum[x] = sum[lc]; add(sum[x], sum[rc]); } void update(int x, int l, int r, int tl, int tr, int val) { if (l > tr || tl > r) RE; if (l >= tl && r <= tr) { pd(x, val); RE; } int mid = (l + r) >> 1; pushdown(x); update(lc, l, mid, tl, tr, val); update(rc, mid + 1, r, tl, tr, val); sum[x] = sum[lc]; add(sum[x], sum[rc]); } int get(int x, int l, int r, int tl, int tr) { if (l > tr || tl > r) RE 0; if (l >= tl && r <= tr) RE sum[x]; int mid = (l + r) >> 1; pushdown(x); RE(get(lc, l, mid, tl, tr) + get(rc, mid + 1, r, tl, tr)) % mod; } } T1, T2, Tr; int a[300005], pw[300005]; P<int, int> p[300005]; int val1[300005], val2[300005]; signed main() { // freopen("diary.in", "r", stdin); // freopen("diary.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; FOR(i, 1, n) cin >> a[i], p[i] = MP(a[i], i); sort(p + 1, p + n + 1); reverse(p + 1, p + n + 1); int inv = POW(k, mod - 2); int mul = 1; FOR(i, 1, n) { mul = 1ll * mul * k % mod; num[i] = mul; } T1.build(1, 1, n); mul = 1; for (int i = n; i >= 1; i--) { mul = 1ll * mul * k % mod; num[i] = mul; } T2.build(1, 1, n); pw[0] = 1; FOR(i, 1, n) pw[i] = 1ll * pw[i - 1] * inv % mod, T.update(i, 1); FOR(i, 1, n) { int x = p[i].S; int tl = T.get(x), tr = (n - i + 1) - T.get(x - 1); val1[x] = 1ll * T2.get(1, 1, n, 1, x) * pw[tr] % mod * p[i].F % mod; val2[x] = 1ll * T1.get(1, 1, n, x, n) * pw[tl] % mod * p[i].F % mod; T2.update(1, 1, n, 1, x, inv); T1.update(1, 1, n, x, n, inv); T.update(x, -1); } FILL(num, 0); FOR(i, 1, n) { if (a[i] < B) Tr.update(1, 1, B, a[i] + 1, B, k); Tr.ins(1, 1, B, a[i], val1[i]); pre[i] = Tr.sum[1]; add(pre[i], pre[i - 1]); } Tr.build(1, 1, B); for (int i = n; i >= 1; i--) { Tr.update(1, 1, B, a[i], B, k); Tr.ins(1, 1, B, a[i], val2[i]); suf[i] = Tr.sum[1]; add(suf[i], suf[i + 1]); } FOR(_, 1, m) { int l, r; cin >> l >> r; cout << (0ll + pre[n] - pre[l - 1] - suf[r + 1] + mod + mod) % mod * k % mod << '\n'; } RE 0; }