import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author lewin
 */
public class pcfg_lewin {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader2 in = new InputReader2(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        PermutationContextFreeGrammar solver = new PermutationContextFreeGrammar();
        solver.solve(1, in, out);
        out.close();
    }

    static class PermutationContextFreeGrammar {
        int n;
        int t;
        int q;
        long INF = (long) 1e9;

        public void solve(int testNumber, InputReader2 in, OutputWriter out) {
            n = in.nextInt();
            t = in.nextInt();
            q = in.nextInt();
            int[] perm = in.readIntArray(n);
            for (int i = 0; i < n; i++) perm[i]--;

            PermutationContextFreeGrammar.Query[] qs = new PermutationContextFreeGrammar.Query[q];
            for (int i = 0; i < q; i++) {
                qs[i] = new PermutationContextFreeGrammar.Query(in.nextInt() - 1, in.nextLong() - 1, i, n);
            }

            long mod = INF;
            while (!BigInteger.valueOf(mod).isProbablePrime(20)) mod++;

            long[][] len = new long[t + 1][n];
            long[][] lenmod = new long[t + 1][n];
            len[0][0] = 1;
            lenmod[0][0] = 1;
            for (int i = 1; i <= t; i++) {
                len[i][0] = 1;
                lenmod[i][0] = 1;
                for (int j = 1; j < n; j++) {
                    len[i][j] = len[i - 1][j] + len[i][j - 1];
                    if (len[i][j] >= INF) len[i][j] = INF;
                    lenmod[i][j] = lenmod[i - 1][j] + lenmod[i][j - 1];
                    if (lenmod[i][j] >= mod) lenmod[i][j] -= mod;
                }
            }
            long[][] comb = new long[n + 1][t + 1];
            comb[0][0] = 1;
            for (int i = 1; i <= n; i++) {
                comb[i][0] = 1;
                for (int j = 1; j <= i && j < t; j++) {
                    comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
                    if (comb[i][j] >= mod) comb[i][j] -= mod;
                }
            }
            List<PermutationContextFreeGrammar.Element>[] elem = LUtils.genArrayList(n);
            BITLong bt = new BITLong(n + 1);
            int[] lo = new int[q], hi = new int[q];
            int[] qlast = new int[n];
            int[] qprev = new int[q];
            int[] qadj = new int[q];
            for (int j = t; j >= 1; j--) {
                Arrays.fill(lo, 0);
                Arrays.fill(hi, n - 1);
                while (true) {
                    boolean added = false;
                    Arrays.fill(qlast, -1);
                    int qid = 0;
                    for (int i = 0; i < q; i++) {
                        if (lo[i] != hi[i]) {
                            int mid = (lo[i] + hi[i]) / 2;
                            qadj[qid] = i;
                            qprev[qid] = qlast[mid];
                            qlast[mid] = qid++;
                            added = true;
                        }
                    }
                    if (!added) break;
                    for (int i = 0; i < n; i++) {
                        bt.update(perm[i], len[j][perm[i]]);
                        for (int q = qlast[i]; q != -1; q = qprev[q]) {
                            int qi = qadj[q];
                            if (bt.query(qs[qi].cap) > qs[qi].a) {
                                hi[qi] = i;
                            } else {
                                lo[qi] = i + 1;
                            }
                        }
                    }
                    bt.clear();
                }

                Arrays.fill(qlast, -1);
                int qid = 0;
                for (int i = 0; i < q; i++) {
                    qadj[qid] = i;
                    qprev[qid] = qlast[lo[i]];
                    qlast[lo[i]] = qid++;
                }

                boolean[] seen = new boolean[n];
                for (int i = 0; i < n; i++) {
                    seen[perm[i]] = true;
                    for (int q = qlast[i]; q != -1; q = qprev[q]) {
                        int qi = qadj[q];
                        if (qs[qi].cap >= qs[qi].k) {
                            if (j == 1 && seen[qs[qi].k]) qs[qi].ans++;
                            else elem[i].add(new PermutationContextFreeGrammar.Element(qs[qi].k, qs[qi].cap, qi, j));
                        }

                        qs[qi].a -= bt.query(qs[qi].cap);
                        qs[qi].cap = perm[i];
                    }
                    bt.update(perm[i], len[j][perm[i]]);
                }
                bt.clear();
            }

            BITModLong[] bm = new BITModLong[t];
            for (int a = 0; a < t; a++) bm[a] = new BITModLong(n + 1, mod);
            for (int i = 0; i < n; i++) {
                for (PermutationContextFreeGrammar.Element e : elem[i]) {
                    long add = 0;
//                for (int a = 0; a < i; a++) {
//                    if (perm[a] >= e.k && perm[a] <= e.cap) {
//                        add += len[e.j - 1][perm[a] - e.k];
//                    }
//                }
                    for (int a = 0; a < e.j; a++)
                        add += ((a & 1) == 0 ? +1 : -1) * (bm[e.j - a - 1].query(e.cap) - bm[e.j - a - 1].query(e.k - 1)) * comb[e.k][a];
                    add %= mod;
                    if (add < 0) add += mod;
                    qs[e.idx].ans += add;
                }
                for (int a = 0; a < t; a++) bm[a].update(perm[i], lenmod[a][perm[i]]);
            }
            for (int i = 0; i < q; i++) out.println(qs[i].ans);
        }

        static class Query {
            public int k;
            public int idx;
            public long a;
            public long ans;
            public int cap;

            public Query(int k, long a, int idx, int cap) {
                this.k = k;
                this.a = a;
                this.idx = idx;
                this.cap = cap;
                this.ans = 0;
            }

            public String toString() {
                return "Query{" +
                        "k=" + k +
                        ", idx=" + idx +
                        ", a=" + a +
                        ", ans=" + ans +
                        ", cap=" + cap +
                        '}';
            }

        }

        static class Element {
            public int k;
            public int cap;
            public int idx;
            public int j;

            public Element(int k, int cap, int idx, int j) {
                this.k = k;
                this.cap = cap;
                this.idx = idx;
                this.j = j;
            }

            public String toString() {
                return "Element{" +
                        "k=" + k +
                        ", cap=" + cap +
                        ", idx=" + idx +
                        ", j=" + j +
                        '}';
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }

    static class InputReader2 {
        private BufferedReader in;
        private StringTokenizer st;

        public InputReader2(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

    }

    static class LUtils {
        public static <E> List<E>[] genArrayList(int size) {
            return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
        }

    }

    static class BITLong {
        private long[] tree;
        private int N;

        public BITLong(int N) {
            this.N = N;
            this.tree = new long[N + 3];
        }

        public long query(int K) {
            K += 2;
            long sum = 0;
            for (int i = K; i > 0; i -= (i & -i)) {
                sum += tree[i];
            }
            return sum;
        }

        public void update(int K, long val) {
            K += 2;
            for (int i = K; i < tree.length; i += (i & -i)) {
                tree[i] += val;
            }
        }

        public void clear() {
            Arrays.fill(tree, 0);

        }

    }

    static class BITModLong {
        public long mod;
        private long[] tree;
        private int N;

        public BITModLong(int _N, long mod) {
            this.N = Integer.highestOneBit(_N + 3) << 1;
            this.mod = mod;
            this.tree = new long[N];
        }

        public long query(int K) {
            K += 2;
            if (K <= 0) return 0;
            long sum = 0;
            for (int i = K; i > 0; i -= (i & -i)) {
                sum += tree[i];
                if (sum >= mod) sum -= mod;
            }
            return sum;
        }

        public void update(int K, long val) {
            K += 2;
            for (int i = K; i < tree.length; i += (i & -i)) {
                tree[i] += val;
                if (tree[i] >= mod) tree[i] -= mod;
            }
        }

    }
}