题目背景

小 X 最喜欢甜品了！

马上就要开学了，但是小 X 并没有写完作业，他十分悲伤地走在街上。忽然，他发现了一家新开的甜品店，悲伤的心情一消而散，随即信步走进甜品店。

题目描述

小 X 发现，店里总共有 $n$ 种甜品，而他想挑选其中的 $k$ 种，并按照一定的顺序来品尝。

每种甜品都有一个美味值 $a_i$，小 X 吃甜品的顺序是有讲究的，他不想使连续两种甜品之间的美味值相差太小，不然他将无法品味出两种甜品之间的差别；但他也不想使连续两种甜品之间的美味值相差太大，否则他将受不了这巨大的味觉冲击。他十分纠结，不知道该如何选择，于是他向你求助。

你要从 $n$ 种甜品中选择 $k$ 种甜品，并且第 $i$ 种甜品（ $i \in [ 2 , k ]$）需要满足如下两个条件：

• 第 $i$ 种甜品的美味值必须大于等于第 $i-1$ 种甜品的 $l$ 倍。

• 第 $i$ 种甜品的美味值必须小于等于第 $i-1$ 种甜品的 $r$ 倍。

问现在你有多少种方案？$k$ 种甜品的美味值之和最大为多少？

因为答案太大，所以两个问题你都需要对 $1000000007$($10^9+7$) 取模。

注：方案总数只考虑 $k$ 种甜品的搭配，不考虑排列顺序。即若存在某 $k$ 种甜品，按照不同顺序品尝都满足条件，仍然只算一种方案。

输入格式

第一行：四个正整数：$n,k,l,r$。

第二行：$n$ 个正整数：$a_i$。

输出格式

第一行一个整数，表示总方案数。

第二行一个整数，表示美味值之和的最大值。

若没有答案，均直接输出 $0$ 。

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

提示

【样例解释】

样例1：只能选 $(4,3,1)$，共 $1$ 种。

样例2：$(1,2)$ 或 $(3,4)$ 或 $(4,5)$，共 $3$ 种。美味值之和最大的是 $(4,5)$，为 $100$。

---

【 数据范围】 | 测试点编号 | $n\le$ | $k\le$ | $a_i\le$ | | :----------: | :----------: | :----------: | :----------: | |$1 \sim 4$ | $20$ | $3$ | $100$ | | $5 \sim 8$ | $10^3$ | $4$ | $10^3$ | | $9 \sim 12$ | $10^5$ | $10$ | $10^5$ | | $13 \sim 16$ | $2\times 10^6$ | $10$ | $10^9$ | | $17 \sim 20$ | $2\times 10^6$ | $10$ | $10^9$ |

• 对于 $90\%$ 的数据，$a_i$ 随机生成。
• 对于 $100\%$ 的数据，$k \le 10$，$k \le n \le 2\times 10^6$，$1 \le l \le r \le 10$，$a_i \le 10^9$。