你需要购买 $m$ 罐薯片。共有 $n$ 家不同的商店，每家商店都有足够的薯片满足你的需求。第 $i$ 家商店单罐薯片的价格为 $a_i$。你不希望单罐价格超过 $B$，因此如果某家商店 $j$ 的价格 $a_j > B$，则该价格对你而言是“不合理”的；否则，该价格是“合理”的。

你可以按任意顺序访问商店，但每家商店最多只能访问一次。

假设你访问商店 $j$ 时还需要购买 $k$ 罐薯片。如果该商店的价格是合理的（$a_j \le B$），你会在该商店购买 $k$ 罐薯片，然后回家，不再访问任何后续商店。否则，你只购买一罐薯片，如果还需要购买更多薯片，则继续前往下一家商店。

一旦你买够了 $m$ 罐薯片，购物行程即告结束。题目保证至少有 $m$ 家商店，因此购物过程必然会结束。

计算你所花费硬币数量的期望值，假设每种购物计划出现的概率相等。形式化地说，这意味着访问 $n$ 家商店的每一种排列被选中的概率相同。答案必须表示为最简分数 $\frac{p}{q}$，其中 $q > 0$ 且 $\gcd(p, q) = 1$。

输入格式

第一行包含三个整数：$n, m$ 和 $B$ ($1 \le m \le n \le 8 \cdot 10^5, 1 \le B \le 5 \cdot 10^6$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 是第 $i$ 家商店单罐薯片的价格 ($1 \le a_i \le 5 \cdot 10^6$)。

输出格式

设 $\frac{p}{q}$ 为你所花费硬币数量的期望值，其中 $q > 0$ 且 $\gcd(p, q) = 1$。请在第一行输出 $p$，在第二行输出 $q$。

样例

样例输入 1

3 2 4
2 3 4

样例输出 1

6
1

样例输入 2

7 3 3
7 6 5 4 3 2 1

样例输出 2

47
5

样例输入 3

11 5 16
20 21 23 10 6 19 5 5 25 27 14

样例输出 3

50329
924