题目描述

贝西有$\red{T}$种蚂蚁共$\red{A}$只，每种蚂蚁有$\red{N_i}$只，同种蚂蚁不能区分，不同种蚂蚁可以区分，记$\red{Sum_i}$为$\red{i}$只蚂蚁构成不同的集合的方案数，问$\red{Sum_k（}$$\red{S≤}$$\red{k≤}$$\red{B）}$之和。

输入格式

第$\red{1}$行：$\red{4}$个空格分隔整数：$\red{T}$、$\red{A}$、$\red{S}$和$\red{B}$

第$\red{2...A+1}$行：每行包含一个整数，该整数是蜂巢中存在的蚂蚁类型

输出格式

第$\red{1}$行：大小$\red{S}$的集合数$\red{S...B}$（包括）可以创建的。

像$\red{{1,2}}$这样的集合与集合$\red{{2,1}}$相同，不应重复计数。只打印此数字的最后六位，不带前导零或空格。

样例

输入样例

3 5 2 3
1
2
2
1
3

输出样例

10

提示

输入详细信息：

三种蚂蚁$\red{（1...3）}$；总共$\red{5}$只蚂蚁。多少套尺寸为$\red{2}$或可以制作$\red{3}$号吗？

输出详细信息：

$\red{5}$组有两个成员的蚂蚁；还有$\red{5}$组三人蚂蚁