Morty Buys Groceries

Rick and Morty went to a store. As you may have figured out, Rick loves giving Morty all kinds of tasks, and this time is no exception. He needs Morty to count the ways to buy $k$ products. The store has $n$ products in total, and the cost of the $i$-th product is $c_i$. Rick will give Morty two numbers $l$ and $r$ a total of $q$ times. For each pair, Morty must say how many ways there are to buy $k$ products whose total cost is at least $l$ and at most $r$.

A purchase is written as a set of indices $\{i_1, i_2, \dots, i_k\}$, where $i_j$ is the number of the product bought $j$-th. Two purchases $A$ and $B$ are different if there is an index $d$ such that $A_d \neq B_d$. So $(1, 2)$ and $(2, 1)$ are two different ways to buy. Also, one product can be bought any number of times.

The first line contains three integers $n$, $k$, $q$ ($1 \leq n, q \leq 10^5$, $1 \leq k \leq 10^5$). The second line contains $n$ integers $c_i$, the costs of the products ($1 \leq c_i \leq 5 \cdot 10^4$). Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \leq l \leq r \leq 5 \cdot 10^4$).

Print the answers to Rick's $q$ queries, one per line. Since the answer can be very large, print it modulo $786433$.