题目描述

贝西有一天在蚁丘旁观察蚂蚁们来回搬运食物时注意到，许多蚂蚁是兄弟姐妹，彼此难以区分。她还发现，有时只有一只蚂蚁去觅食，有时几只，有时则是全部。这形成了大量不同的蚂蚁组合！

出于数学兴趣，贝西开始思考：假设蚁巢有$T$个蚂蚁家族（编号$1$到$T$），总共有$A$只蚂蚁。每个家族有$Ni$只蚂蚁$（1 ≤ Ni ≤ 100）$。那么，可以组成多少组大小为$S$到$B（1 ≤ S ≤ B ≤ A）$的蚂蚁集合？

例如，观察到一个蚂蚁组合包含家族{$1, 1, 2, 2, 3$}（顺序不一定如此）。可能的蚂蚁集合如下：

• 大小为$1$的集合：{$1$}, {$2$}, {$3$}（共$3$个）
• 大小为$2$的集合：{$1,1$}, {$1,2$}, {$1,3$}, {$2,2$}, {$2,3$}（共$5$个）
• 大小为$3$的集合：{$1,1,2$}, {$1,1,3$}, {$1,2,2$}, {$1,2,3$}, {$2,2,3$}（共$5$个）
• 大小为$4$的集合：{$1,2,2,3$}, {$1,1,2,24$}, {$1,1,2,3$}（共$3$个）
• 大小为$5$的集合：{$1,1,2,2,3$}（共$1$个）

你的任务是计算给定数据下可以组成的所有可能集合数量。

输入格式

• 第$1$行：$4$个用空格分隔的整数$T$（家族数）、$A$（总蚂蚁数）、$S$（最小集合大小）、$B$（最大集合大小）
• 第$2$行到第$A+1$行：每行一个整数，表示蚁巢中存在的蚂蚁类型

输出格式

• 第$1$行：可以组成的大小为$S$到$B$（含）的集合数量。输出结果的最后六位数字（不含前导零或空格）

输入样例

3 5 2 3
1
2
2
1
3

输出样例

10

提示

输入解释： 共有3种蚂蚁类型（1到3），总共有5只蚂蚁。可以组成多少大小为2或3的集合？

输出解释： 5个大小为2的集合；5个大小为3的集合。总数为10。

来源

USACO 2005年11月银组