题目描述

为保障城市数据中心的稳定运行，工程师小信需要对一批服务器的存储模块进行性能优化。这批存储模块共有 $n$ 个，每个模块初始的最大数据传输速率不同，分别为正整数 $a_1, a_2, \dots, a_n$。

数据中心的业务要求所有存储模块需协同工作，而整体的传输效率由速率最小的模块决定——若某模块速率过低，会导致整个数据链路卡顿。为解决这一问题，小信可以使用专用的性能增强工具对模块进行升级：每次操作可选中一个模块，将其传输速率提升至原来的 $x$ 倍（$x$ 为工具固定的增强系数，且为正整数），但由于设备功率限制，该工具最多只能进行 $m$ 次操作。

为让整个存储系统的协同效率最优，小信需要规划这 $m$ 次操作的目标模块，使得操作完成后，所有存储模块中速率最小的那个，其数值能达到最大可能值。请你协助小信计算这个最大的最小速率。

由于答案值可能比较大，输出答案对 $10^9+7$ 取模后的结果。
注意：只需要对结果取模，不影响过程计算。

输入格式

第一行包含三个正整数 $n$, $m$, $x$，分别表示模块个数、操作次数和增强系数。
第二行包含 $n$ 个正整数，表示初始传输速率 $a_1, a_2, \dots, a_n$。

输出格式

输出一个正整数，表示经过最优操作规划后，所有存储模块中速率最小的那个的最大可能值，答案需要对 $10^9+7$ 取模。

样例

Input 1

5 4 2
1 3 2 8 10

Output 1

4

Input 2

8 10 2
6 9 12 10 7 5 2 1

Output 2

9

数据范围

• 对于 $10\%$ 的数据，所有的 $a_i$ 全相同。
• 对于另外 $10\%$ 的数据，保证结果取模前小于 $10^9+7$。
• 对于另外 $10\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq m \leq 10^3$。
• 对于另外 $30\%$ 的数据，$1 \leq n \leq 100$。
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq m, x \leq 10^9$，$1 \leq a_i \leq 10^9$。

样例解释

对于样例 1：
初始序列为 $[1, 3, 2, 8, 10]$，进行 $4$ 次操作：

• 第 $1$ 次操作后序列变为 $[2, 3, 2, 8, 10]$；
• 第 $2$ 次操作后序列变为 $[4, 3, 2, 8, 10]$；
• 第 $3$ 次操作后序列变为 $[4, 6, 2, 8, 10]$；
• 第 $4$ 次操作后序列变为 $[4, 6, 4, 8, 10]$。
  最终序列的最小值为 $4$。