Problem Description

ducati loves defining some strange things.

• Two sequences are defined to be different if and only if their lengths are different, or they have the same length but there exists at least one position where the corresponding values are different.

• The weight of a sequence $A$ is defined as the product of all numbers in $A$.

• The reachability between sequences is defined as follows:

  • Perform exactly $t$ operations. In each operation, choose a subarray of $A$ (note that the chosen subarray can be empty) and add $1$ to every number in the subarray. If there exists an operation plan such that after all operations, $A$ becomes exactly the same as $B$, then we say $A$ can reach $B$.

• The elegance value of sequence $A$ is defined as the sum of the weights of all different sequences that are reachable from $A$.

Now, ducati has a sequence $a$ of length $n$. He will query the elegance value of an interval many times.

Can you help this curious person? You only need to output each answer modulo $10007$.

Input Format

The first line contains three integers $n,q,t$, representing the length of the sequence, the number of queries, and the number of allowed modifications in each query.

The second line contains $n$ integers, representing the sequence $a$.

The next $q$ lines each contain two positive integers $l,r$, describing one query.

Output Format

For each query, output the answer modulo $10007$.

2 1 1
1 2
1 2

15

10 3 3
1 5 3 2 2 4 6 3 2 3
1 7
4 9
3 10

3850
1166
3893

Hint

[Sample Explanation 1]

$a$ is $\{1,2\}$. There is a total of $1$ query.

All $b$ that $a$ can reach are as follows:

The sum of their weights is $3+4+6+2=15$.

[Sample Explanation 2]

For the second sample, I have a wonderful explanation, but unfortunately this space is too small, so I cannot write it down.

[Constraints]

This problem uses bundled testdata.

• Subtask1 (10pts): $n,q\le8$;
• Subtask2 (20pts): $q=1$;
• Subtask3 (30pts): $n,q\le5\times10^4$, $t\le2$;
• Subtask4 (40pts): no special constraints.

For $100\%$ of the testdata, $1\le n,q\le10^5$, $1\le a_i\le10^4$, $1\le t\le3$, and for all queries, $1\le l\le r\le n$.

Translated by ChatGPT 5