405012: GYM101741 B Expected Shopping

You want to buy m cans of chips. There are n different shops, and each shop has enough cans of chips to cover your needs. The price of a single can of chips at i-th shop is a_i coins. You don't like to pay more than B coins for a can, so if at some shop j the price of a can is a_j > B, then for you this price is unreasonable. Otherwise, it is reasonable.

You may visit shops in arbitrary order, but each shop can be visited no more than once.

Let us assume that you visit shop j and you still need to buy k cans of chips. If the price at this shop is reasonable (a_j ≤ B), then you buy k cans at this shop and go home without visiting any shop afterwards. Otherwise, you buy only one can of chips, and if you still need to buy some cans, you proceed to the next shop.

As soon as you have m cans of chips, you finish your shopping trip. It is guaranteed that there are at least m shops, so this has to happen eventually.

Calculate the expected number of coins you will spend if each possible shopping plan is equiprobable. Formally, this means that each permutation of n numbers denoting the order in which you plan to visit the shops has the same probability of being chosen. The answer must be calculated as a rational fraction , where q > 0 and .

The first line contains three integers: n, m, and B (1 ≤ m ≤ n ≤ 8·10⁵, 1 ≤ B ≤ 5·10⁶).

The second line contains n integers a₁, a₂, ..., a_n, where a_i is the price of a single can of chips at i-th shop (1 ≤ a_i ≤ 5·10⁶).

Let p and q be the numbers such that is the expected number of coins you will spend, q > 0 and . Print p on the first line and q on the second line of the output.

3 2 4
2 3 4

6
1

7 3 3
7 6 5 4 3 2 1

47
5

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

50329
924