时间限制：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时，即 1 名同学组成的队伍有 3 种组合：{1}，{2}，{3}
　　◆ 当S=2时，即 2 名同学组成的队伍有 5 种组合：{1,1}，{1,2}，{1,3}，{2,2}，{2,3}
　　◆ 当S=3时，即 3 名同学组成的队伍有 5 种组合：{1,1,2}，{1,1,3}，{1,2,2}，{1,2,3}，{2,2,3}
　　◆ 当S=4时，即 4 名同学组成的队伍有 3 种组合：{1,2,2,3}，{1,1,2,2，{1,1,2,3}
　　◆ 当S=5时，即 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