测试数据来自 system/2138

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物。很快贝茜发现有些蚂蚁长的几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家庭里的成员。她发现整个蚂蚁群里有时只有一只出来觅食，有时是几只，有时干脆整个蚂蚁群一起出来。这样一来，蚂蚁们出行觅食时的组队方案就有很多种。

　　做为一头有数学头脑的奶牛，贝茜注意到整个蚂蚁群由 \(T\) 个家庭组成，她将这些家族按 \(1..T\) 依次编号，编号为 \(i\) 的家族里有 \(N_i\) 只蚂蚁。同一个家族里的蚂蚁可以认为是完全相同的。

　　如果一共有 \(S,S+1,…,B（1 ≤ S ≤ B ≤ A）\) 只蚂蚁一起出来觅食，它们一共能组成多少种不同的队伍呢？注意：只要两支队伍中所包含的所有家族的蚂蚁数量都相同时，即使有某个家族换了几只蚂蚁出来，贝茜也会因为看不出不同而认为他们是同一支队伍。

　　比如说，有 3 个家族组成蚂蚁群里一共有 5 只蚂蚁，他们所属的家族分别为 1,1,2,2,3。于是出去觅食时候他们有以下几种组队方案：

　　◆ 1 只蚂蚁出去有 3 种组合：{1}，{2}，{3}
　　◆ 2 只蚂蚁出去有 5 种组合：{1,1}，{1,2}，{1,3}，{2,2}，{2,3}
　　◆ 3 只蚂蚁出去有 5 种组合：{1,1,2}，{1,1,3}，{1,2,2}，{1,2,3}，{2,2,3}
　　◆ 4 只蚂蚁出去有 3 种组合：{1,2,2,3}，{1,1,2,2，{1,1,2,3}
　　◆ 5 只蚂蚁出去有 1 种组合：{1,1,2,2,3}

　　你的任务就是根据给出的数据，计算蚂蚁们的组队方案总数。

【输入格式】

　　第一行包含四个整数：\(T,A,S,B\)。
　　第 \(2\) 到 \(A+1\) 行：每行是一个正整数，为每只蚂蚁所在的家族编号。

【输出格式】

　　输出一个整数，表示 \(S\) 到 \(B\)（包含 \(S\) 和 \(B\)）只蚂蚁出去觅食时，不同的组队方案。最后的可能答案很大，你只需要输出答案的最后 6 位数字。注意不要输出前导 0 以及多余的空格。

【输入输出样例】

　Input

3 5 2 3
1
2
2
1
3

　Output

10

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤T≤1000\)，\(1≤N_i≤100\)。

【来源】

　　Mr.he