3846 - 甜品

小 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 。

【样例解释】

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

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

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

EZEC