P7576 「PMOI-3」期望乘积

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$ 取模的值。

【样例解释1】 $a$ 为 $\{1,2\}$。共 $1$ 次询问。 所有 $a$ 可达的 $b$ 如下： $$\{1,3 \} \{2,2 \} \{2,3 \}\{1,2 \}$$ 它们的权值之和为 $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$。