样例下载

题目描述

有 $N$ 个小球，第 $i$ 个小球的颜色为 $C_i$。颜色的种类不超过 $K$。同一种颜色的小球不超过 $100$ 个。同一种颜色的小球被认为是没有区别的。

现在小明要选出若干个小球装入到一个盒子中。

小明打算装入至少 $A$ 个小球，至多 $B$ 个小球。

问：小明有多少种装盒方案？

答案可能很大，你需要输出答案 $mod$ $10^6$。

输入格式

第一行：包含四个整数 $K，N，A，B$.

接下来 $N$ 行：每行包含一个整数 $C_i$，表示第 $i$ 个小球的颜色。

输出格式

一个整数，表示答案 $mod$ $10^6$

样例输入

3 5 1 3
1
2
2
1
3

样例输出

13

样例解释

样例中共 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}

一共有 3 + 5 + 5 = 13 种方案。

数据范围

$1 ≤ K ≤ 10^3, 1 ≤ N ≤ 10^5, 1 ≤ A ≤ B ≤ N, 1 ≤ C_i ≤ K$