T466374 随机取数

有一个长度为$n$的序列$A_{1 \ldots n}$，现在白云想做$Q$次操作，初始$ans=0$ 每一次操作，从$[1,m]$中随机一个整数$x$，然后找到序列$A$中最小的大于等于$x$的数。如果能找到，则$ans+=x$，然后把这个数删除，如果找不到就跳过 现在，你需要求出$Q$次操作以后，$ans$的期望是多少

第一行三个整数$n,m,Q$。 第二行$n$个整数$a_{1 \ldots n}$

输出答案，对1000109107取模。 答案一定是一个有理数，假设为$\frac{x}{y}$的形式，你只需要输出一个数$ans$满足$ans * y \equiv x (mod \ 1000109107)$。

**【样例 1 解释】** 答案为$\frac{102}{3^3} \equiv 222246472$ **【数据范围】** - 对于前$10\%$的数据，有$1 \le n,m,Q \le 5$。 - 对于前$20\%$的数据，有$1 \le n,m,Q \le 15$。 - 对于前$40\%$的数据，有$1 \le n,m,Q \le 50$。 - 对于另外$20\%$的数据，有$1 \le m,q \le 10$。 - 对于另外$20\%$的数据 (不包括上一个部分分)，有$1 \le m \le 10$。 - 对于$100\%$的数据，有$1 \le n,Q \le 100$，$1 \le a_i \le M \le 200$。