Background

X likes desserts the most.

School is about to start, but X has not finished his homework. He walks sadly on the street. Suddenly, he finds a newly opened dessert shop, and his sadness disappears. He then walks into the dessert shop.

Problem Description

X finds that there are a total of $n$ kinds of desserts in the shop. He wants to pick $k$ of them and taste them in a certain order.

Each dessert has a deliciousness value $a_i$. X is picky about the eating order: he does not want the deliciousness values of two consecutive desserts to differ by too little, otherwise he cannot tell the difference between them; but he also does not want them to differ by too much, otherwise the huge taste impact will be unbearable. He is very conflicted and does not know how to choose, so he asks you for help.

You need to choose $k$ desserts from the $n$ desserts, and for the $i$-th dessert ($i \in [2, k]$), it must satisfy the following two conditions:

• The deliciousness value of the $i$-th dessert must be greater than or equal to $l$ times that of the $(i-1)$-th dessert.
• The deliciousness value of the $i$-th dessert must be less than or equal to $r$ times that of the $(i-1)$-th dessert.

How many valid selections are there? What is the maximum possible sum of deliciousness values among the $k$ chosen desserts?

Since the answers may be too large, you need to take both results modulo $1000000007$ ($10^9+7$).

Note: The number of selections only considers which $k$ desserts are chosen, and does not consider the order. That is, if there exists a set of $k$ desserts such that tasting them in different orders all satisfies the conditions, it is still counted as only one selection.

Input Format

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

The second line contains $n$ positive integers: $a_i$.

Output Format

The first line contains one integer, the total number of valid selections.

The second line contains one integer, the maximum sum of deliciousness values.

If there is no valid selection, output $0$ for both lines.

4 3 2 3
7 5 3 1

1
11

5 2 4 4
1 4 5 20 80

3
100

20 3 2 5
88 24 35 53 5 44 45 30 29 43 46 33 21 24 64 43 23 71 63 53 

33
153

5 5 2 4
1 2 3 4 5

0
0

Hint

[Sample Explanation]

Sample 1: You can only choose $(4, 3, 1)$, so there is $1$ selection.

Sample 2: $(1, 2)$ or $(3, 4)$ or $(4, 5)$, so there are $3$ selections. The maximum sum of deliciousness values is $(4, 5)$, which is $100$.

[Constraints]

• For $90\%$ of the testdata, $a_i$ is randomly generated.
• For $100\%$ of the testdata, $k \le 10$, $k \le n \le 2\times 10^6$, $1 \le l \le r \le 10$, $a_i \le 10^9$.

Translated by ChatGPT 5