题目描述

ducati 热爱定义一些奇奇妙妙的东西。

• 定义两个序列不同，当且仅当它们的长度不同，或者它们长度相同但存在至少一组对应位上的值不同。

• 定义序列 $A$ 的权值为 $A$ 中所有数的乘积。

• 定义序列间的可达如下：

  • 做恰好 $t$ 次操作，每次操作选择 $A$ 的一个子区间（注意，选定的子区间可以为空）并将子区间中的数加 $1$ ；若存在一种操作方案，使得操作结束后 $A$ 与 $B$ 完全相同 ，则称 $A$ 可达 $B$。

• 定义序列 $A$ 的优美值为 $A$ 可达的所有不同序列的权值和。

现在，ducati 拥有了一个长度为 $n$ 的序列 $a$。他会多次查询一段区间的优美值。

你能帮帮好奇的他吗？你只需要输出每个答案对 $10007$ 取模的值就行啦。

输入格式

第一行三个整数 $n,q,t$，表示序列的长度、询问的次数与每次询问的可修改次数。

第二行 $n$ 个整数，表示序列 $a$。

下面 $q$ 行，每行两个正整数 $l,r$，描述一次询问。

输出格式

对于每次询问，输出答案对 $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

提示

【样例解释1】

$a$ 为 $\{1,2\}$。共 $1$ 次询问。

所有 $a$ 可达的 $b$ 如下：

它们的权值之和为 $3+4+6+2=15$ 。

【样例解释2】

关于第二个样例，我有一个绝妙的解释，可惜这里空白太小，我写不下。

【数据范围】

本题采用捆绑测试。

• Subtask1（10pts）：$n,q\le8$；
• Subtask2（20pts）：$q=1$；
• Subtask3（30pts）：$n,q\le5\times10^4$，$t\le2$；
• Subtask4（40pts）：无特殊限制。

对于 $100\%$ 的数据满足，$1\le n,q\le10^5$，$1\le a_i\le10^4$，$1\le t\le3$，对于所有询问，$1\le l\le r\le n$。