题目描述

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

输入格式

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

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

输出格式

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

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

样例

输入样例

3 5 2 3
1
2
2
1
3

输出样例

10

提示

输入详细信息：

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

输出详细信息：

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