Dessert Selection

You are given $n$ desserts, each with a deliciousness value $a_i$. You want to choose exactly $k$ desserts from these $n$ and arrange them in an order for tasting. However, the tasting order must satisfy the following conditions for every $i$ ($2\le i\le k$):

[ \text{(1) } a_i \geq l \times a_{i-1}, \quad \text{(2) } a_i \leq r \times a_{i-1}. ]<br>
Note: In counting the number of valid selections, different tasting orders of the same set of $k$ desserts are considered as one unique combination.

Your task is to compute two values modulo $10^9+7$:

• The number of valid dessert combinations.
• The maximum possible sum of the deliciousness values among all valid combinations.

If no valid combination exists, output both values as 0.

inputFormat

The first line contains four integers: $n$, $k$, $l$, and $r$.

The second line contains $n$ integers, where the $i$-th integer represents $a_i$, the deliciousness value of the $i$-th dessert.

outputFormat

Output two space-separated integers: the number of valid combinations and the maximum sum of deliciousness values among these valid combinations, both taken modulo $10^9+7$.

sample

4 2 1 2
1 2 3 4

4 7