题目描述

​ 有一天， Bessie 无聊地坐在蚂蚁洞前看蚂蚁们进进出出搬运食物。不久， Bessie 发现有些蚂蚁长得几乎一模一样，于是她认为这些蚂蚁是兄弟姐妹关系，也就是说它们是同一个家族里的成员。她也发现，整个蚂蚁群里有时只有一只出来觅⻝，有时则是几只，有时干脆整个蚁群一起出来。这样一来，蚂蚁们出行觅食时的组队方案就有很多种！ ​ 作为一头有数学头脑的奶牛， Bessie 注意到整个蚁群由 T （ 1 <T <1000 ）个家族组成，她将这些家族编号为 $1 \dots T$。每个家族里有 $N_i （ 1 \le N_i \le 100 ）$只蚂蚁。同一个家族里的蚂蚁可以认为是完全相同的。蚁群总共有 A 只蚂蚁。 ​ 如果⼀共有$S, S + 1, \dots, B （ 1 \le S \le B \le A ）$只蚂蚁一起出去觅食，它们一共能组成多少种不同的队伍呢？ ​ 例如，由 3 个家族组成的蚁群里有 5 只蚂蚁，它们所属的家族分别为 {1, 1, 2, 2, 3} ，有以下几种组队方案： ​

• 1 只蚂蚁出去有三种： $\{1\}, \{2\}, \{3\}$ 。
• 2 只蚂蚁出去有五种： $\{1, 1\}, \{1, 2\}, \{1, 3\}, \{2, 2\}, \{2, 3\}$ 。
• 3 只蚂蚁出去有五种： $\{1, 1, 2\}, \{1, 1, 3\}, \{1, 2, 2\}, \{1, 2, 3\}, \{2, 2, 3\} $。
• 4 只蚂蚁出去有三种：$\{1, 2, 2, 3\}, \{1, 1, 2, 2\}$, $\{1, 1, 2, 3\}$ 。
• 5 只蚂蚁出去有一种： $\{1, 1, 2, 2, 3\}$ 。 ​ 根据给出的数据，请你求出蚂蚁们组队出来觅食的方案数。两种组队方案不同当且仅当两种方案所包含的某个家族的蚂蚁数不同。 ​

输入格式

第 $1$ 行：四个整数 $T, A, S, B$ 。 第 $2 \dots A + 1$ 行：每行包括一个整数，表示蚁群中一只蚂蚁所属的家族编号。

输出格式

​ 第 1 行：蚂蚁数量为 $S \dots B$ 时的觅食队伍的方案数。 $\{1, 2\}$ 和 $\{2, 1\}$ 被视为同一种方案。只需输出答案的最后 6 位，并且忽略前导零。 ​

样例

输入样例

3 5 2 3
1
2
2
1
3                                      

输出样例

10                                      

样例解释

一共有 3 个家族和 5 只蚂蚁。蚂蚁数量为 2 时有 5 种方案，蚂蚁数量为 3 时有 5 种方案。