Problem Background

Little X loves desserts the most!

School is about to start, but Little X hasn't finished his homework. He walks sadly on the street. Suddenly, he discovers a newly opened dessert shop. His sad mood dissipates instantly, and he walks into the dessert shop confidently.

Problem Description

Little X finds that the shop has a total of $n$ types of desserts, and he wants to select $k$ of them to taste in a specific order.

Each type of dessert has a deliciousness value $a_i$. Little X is particular about the order in which he eats the desserts. He doesn't want the deliciousness values of two consecutive desserts to differ too much, as he won't be able to taste the difference between them; but he also doesn't want the deliciousness values to differ too much, as he won't be able to handle the huge taste shock. He is very conflicted and doesn't know how to choose, so he turns to you for help.

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

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

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

You need to determine how many such combinations are possible and what the maximum sum of the deliciousness values for these $k$ desserts is.

Since the answers are very large, you need to take the modulo of $1000000007$ ($10^9+7$) for both questions.

Note: The total number of combinations only considers the selection of $k$ types of desserts, not their order. That is, if there are $k$ types of desserts that satisfy the conditions regardless of the order in which they are tasted, they are still considered as one combination.

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 an integer representing the total number of combinations.

The second line contains an integer representing the maximum sum of the deliciousness values.

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

Sample Input and Output

Input Sample #1

4 3 2 3
7 5 3 1

Output Sample #1

1
11

Input Sample #2

5 2 4 4
1 4 5 20 80

Output Sample #2

3
100

Input Sample #3

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

Output Sample #3

33
153

Input Sample #4

5 5 2 4
1 2 3 4 5

Output Sample #4

0
0

Notes

Sample Explanation

Sample 1: Only $(4, 3, 1)$ can be selected, for a total of $1$ combination.

Sample 2: $(1, 2)$ or $(3, 4)$ or $(4, 5)$, for a total of $3$ combinations. The maximum sum of deliciousness values is $(4, 5)$, which is $100$.

Data Range

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

见题面 Input 部分

见题面 Output 部分