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

---

【题目描述】

　　学校共有 \(T\) 个班，用 \(1..T\) 依次编号，编号为 \(i\) 的班有 \(N_i\) 名学生。现在要抽调 \(S,S+1,…,B（1≤S≤B≤A）\)个同学组成参赛队伍，那么一共能组成多少种不同的队伍呢？
　　比如说，有5名同学分属3个不同的班，他们所属的班级分别为 1,1,2,2,3。于是有如下几种组队方案：
　　◆当 \(S=1\) 时，队伍有3种组合：{1}，{2}，{3}
　　◆当 \(S=2\) 时，队伍有5种组合：{1,1}，{1,2}，{1,3}，{2,2}，{2,3}
　　◆当 \(S=3\) 时，队伍有5种组合：{1,1,2}，{1,1,3}，{1,2,2}，{1,2,3}，{2,2,3}
　　◆当 \(S=4\) 时，队伍有3种组合：{1,2,2,3}，{1,1,2,2，{1,1,2,3}
　　◆当 \(S=5\) 时，队伍有1种组合：{1,1,2,2,3}
　　你的任务就是根据给出的数据，计算组队方案总数。

【输入格式】

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

【输出格式】

　　输出一个整数，表示 \(S\) 到 \(B\)（包含 \(S\) 和 \(B\)）名同学出组队时，不同的组队方案之和。最后的可能答案很大，你只需要输出答案的最后 6 位数字。

【输入输出样例】

　Input

3 5 2 3
1
2
2
1
3

　Output

10

【数据限制】

　　对于100% 的数据满足：\(1≤T≤1000，1≤N_i≤100，1≤A≤4000\)。

【来源】

　　Mr.he