Beautiful Reachability

Ducati loves to define some very unusual things. In this problem, we work with sequences and operations defined as follows.

Two sequences are considered different if and only if their lengths differ, or if they have the same length but differ in at least one corresponding position.

For a sequence (A = [A_1, A_2,\dots,A_m]), its weight is defined as [ \text{wt}(A) = \prod_{i=1}^{m} A_i. ]

We say that a sequence (A) is reachable to a sequence (B) if by performing exactly (t) operations on (A), we can obtain (B). In each operation, you choose a subarray (note that the chosen subarray may be empty) and add (1) to every number in that subarray. (An empty subarray means no changes in that operation.)

The beautiful value of a sequence (A) is defined as the sum of the weights of all distinct sequences that are reachable from (A) by exactly (t) operations. Since the value may be huge, you are only required to output it modulo 10007.

Given a sequence (a) of length (n), Ducati will ask you (q) queries. In each query, you are given a subarray (specified by its indices) and you need to compute its beautiful value.

Input/Output Format:

• Input: The first line contains three integers \(n\), \(t\), and \(q\). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\). Each of the following \(q\) lines contains two integers \(l\) and \(r\) indicating that you need to answer the query on the subarray \(a[l \dots r]\) (1-indexed).
• Output: For each query, output the beautiful value of the subarray modulo 10007 on a separate line.

Note: Two sequences are considered different if their lengths differ or if there exists at least one index where their elements differ.

Explanation: Suppose we have a subarray (A) of length (m). An operation consists of picking a subarray of (A) (possibly empty) and adding (1) to each element in that chosen part. After exactly (t) operations, you get a sequence (B = A + D) where (D = [d_1, d_2, \dots, d_m]) is the sum of the chosen addition vectors. The beautiful value is [ \sum_{D \in S} \prod_{i=1}^{m} (A_i + d_i) \mod 10007, ] where (S) is the set of all distinct vectors (D) obtainable by exactly (t) operations.

Constraints (for this version):

• \(1 \le n \le 10\)
• \(0 \le a_i \le 10^9\)
• \(0 \le t \le 3\) (You may assume \(t\) is small.)
• \(1 \le q \le 20\)

inputFormat

The first line contains three integers (n), (t), and (q). The second line contains (n) integers representing the sequence (a_1, a_2, \dots, a_n). Each of the following (q) lines contains two integers (l) and (r) (1-indexed) representing a query subarray.

outputFormat

For each query, output one line containing one integer – the beautiful value of the queried subarray modulo 10007.

sample

3 1 2
1 2 3
1 1
2 3

3
35

</p>