时间限制：1000ms　内存限制：512MB

题目描述

程老师的工厂里有一条装配线，正在为月底的大订单赶工。装配线上固定排着 $n$ 个工件，第 $i$ 个工件的重量是 $a_i$。工件的加工顺序早就定死了——只能按排好的顺序依次处理——但怎么分批，车间还有自主权：工件要按顺序加工成若干批次，每一批是装配线上连续的一段，全部工件恰好被分完，一个不多一个不少。

车间的规矩是从多年教训里总结出来的，十分严格：每批的工件数量必须落在 $[L, R]$ 之间。少于 $L$ 个，机器预热一次不划算，厂规禁止开机；多于 $R$ 个，台面放不下，硬塞会出安全问题。每开一批的成本由两部分组成：一是固定的开机费 $S$——只要点火就得烧这份钱，跟这批装几个工件无关；二是这一批所有工件的重量之和——工件越重，搬运和耗电越多。每批成本是这两者之和，全部批次加起来就是总成本。把成本拆成这两块是有讲究的：开机费管的是"批次数"，重量费管的是"总搬运量"，排产师傅每多开一批就要多掏一份 $S$，所以批怎么划、划几批，里头全是学问。

有些排法下，这样的分批根本无法完成。比如只剩 $3$ 个工件没分而 $L = 2$：拿 $2$ 个开一批，剩下 $1$ 个不够开机；只拿 $1$ 个又违规——再好的师傅也只能干瞪眼。月底盘点时最怕撞上这种情况，得提前算清楚。

老师傅排产时也总有两难：批次开多了，开机费一笔一笔烧着心疼；批次开少了，每批塞太满又违反厂规。何况每批件数还有上下限卡着，稍不留神就排出个违规方案。程老师这个月索性不想靠经验拍脑袋了，他要把所有合法分法都掂量一遍，找出最省钱的那种，顺便数一数最省钱的分法到底有多少种——如果只有一两种，万一机器临时检修还来得及换方案；如果有成千上万种，那排产就从容多了。车间里的年轻人私下都打赌，说最后肯定是按某种"看着舒服"的分法来排，程老师偏要用数字说话。

程老师想知道两个数：完成全部加工的最小总成本，以及达到这个最小成本的不同分批方案数。两种分批方案只要存在一处划分位置不同（比如前一种把第 $3$ 个工件划进第二批，后一种划进第三批），就算不同方案——哪怕两种分法的批次数一样、成本一样，也是两种方案，要分别计数。方案数可能很大，对 $10^9 + 7$ 取模。

输入格式

第一行四个整数 $n, L, R, S$，表示工件数、每批最小件数、每批最大件数和开机费。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每个工件的重量。

输出格式

如果可以完成分批，输出一行两个整数，用空格隔开：最小总成本、达到最小成本的方案数（对 $10^9 + 7$ 取模）。

如果无法完成分批，输出一行 -1。

数据范围

• 特殊性质 A：$L = R$。
• 特殊性质 B：$S = 0$。
• 对于全部数据，$1 \le L \le R \le n \le 10^6$，$0 \le S \le 10^9$，$1 \le a_i \le 10^9$。

样例

样例 1

输入：

5 1 2 10
1 2 3 4 5

输出：

45 3

解释：工件总重量 $15$ 是固定的，无论怎么分批都计入总成本，所以批次越少越省：每批最多 $2$ 件，$5$ 个工件至少要 $3$ 批。按 $3$ 批分，总成本 $15 + 3 \times 10 = 45$。把 $5$ 个工件分成 $3$ 批、每批 $1 \sim 2$ 件的分法有：$(2,2,1)$、$(2,1,2)$、$(1,2,2)$，共 $3$ 种。

样例 2

输入：

3 2 2 1
1 1 1

输出：

-1

解释：每批必须恰好 $2$ 件。第一批拿走 $2$ 个后只剩 $1$ 个，凑不出第二批；先拿 $1$ 个又不符合规矩。无法完成，输出 -1。

样例 3

输入：

5 2 3 0
1 2 3 4 5

输出：

15 2

解释：开机费为 $0$，无论分几批，总成本都等于工件总重量 $15$，所以最小成本就是 $15$。达到它的方案就是所有合法分批：每批 $2 \sim 3$ 件分完 $5$ 个工件，有 $(2,3)$ 和 $(3,2)$ 两种。