题目描述

有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物。很快贝茜发现有些蚂蚁长得几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家族里的成员。她也发现整个蚂蚁群里有时只有一只出来觅食，有时是几只，有时干脆整个蚁群一起出来。这样一来，蚂蚁们出行觅食时的组队方案就有很多种。作为一头有数学头脑的奶牛，贝茜注意到整个蚂蚁群由 $t$ 个家族组成，她将这些家族按 $1$ 到 $t$ 依次编号。编号为 $i$ 的家族里有 $n_i$ 只蚂蚁。同一个家族里的蚂蚁可以认为是完全相同的。如果一共有 $s,s+1 \ldots ,b$ 只蚂蚁一起出去觅食，它们一共能组成多少种不同的队伍呢？注意：只要两支队伍中所包含某个家族的蚂蚁数不同，我们就认为这两支队伍不同。由于贝茜无法分辨出同一家族的蚂蚁，所以当两支队伍中所包含的所有家族的蚂蚁数都相同时，即使有某个家族换了几只蚂蚁出来，贝茜也会因为看不出不同而把它们认为是同一支队伍。比如说，有个由 $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)$。

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

输入格式

第一行：$4$ 个用空格隔开的整数 $t,a,s,b$。

第二行到第 $a+1$ 行：每行是一个正整数，为某只蚂蚁所在的家族的编号。

输出格式

输出一个整数，表示当 $s$ 到 $b$（包括 $s$ 和 $b$）只蚂蚁出去觅食时，不同的组队方案数。

注意：组合是无序的，也就是说组合 $1,2$ 和组合 $2,1$ 是同一种组队方式。最后的答案可能很大，你只需要输出答案的最后 $6$ 位数字，注意不要输出前导 $0$ 以及多余的空格。

5 2 3

10

样例说明 1

$2$ 只蚂蚁外出有 $5$ 种组合，$3$ 只蚂蚁外出有 $5$ 种组合。共有 $10$ 种组合。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n_i \leq 100$，$1 \leq s \leq b \leq a$，$1 \leq t \leq 10^3$。

题目来源

Silver