题目描述

有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物．很快贝茜发现有些蚂蚁长得几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家族里的成员．她也发现整个蚂蚁群里有时只有 一只出来觅食，有时是几只，有时干脆整个蚁群一起出来．这样一来，蚂蚁们出行觅食时的组队方案就有很多种．作为一头有数学头脑的奶牛，贝茜注意到整个蚂蚁群由$\red{T(1≤}$$\red{T≤}$$\red{1000)}$个家族组成，她将这些家族按$\red{1}$到$\red{T}$依次编号．编号为$\red{i}$的家族里有$\red{Ni(1≤}$$\red{Ni≤}$$\red{100)}$只蚂蚁．同一个家族里的蚂蚁可以认为是完全相同的．

如果一共有$\red{S，}$$\red{S+1...，}$$\red{B(1≤}$$\red{S≤}$$\red{B≤}$$\red{A)}$只蚂蚁一起出去觅食，它们一共能组成多少种不同的队伍呢？注意：只要两支队伍中所包含某个家族的蚂蚁数不同， 我们就认为这两支队伍不同．由于贝茜无法分辨出同一家族的蚂蚁，所以当两支队伍中所包含的所有家族的蚂蚁数都相同时，即使有某个家族换了几只蚂蚁出来，贝茜也会因为看不出不同而把它们认为是同一支队伍 ．

比如说，有个由$\red{3}$个家族组成的蚂蚁群里一共有$\red{5}$只蚂蚁，它们所属的家族分别为$\red{1，}$$\red{1，}$$\red{2，}$$\red{2，}$$\red{3}$．于是出去觅食时它们有以下几种组队方案：

·$\red{1}$只蚂蚁出去有三种组合：$\red{(1)(2)(3)}$

·$\red{2}$只蚂蚁出去有五种组合：$\red{(1，}$$\red{1)(1，}$$\red{2)(1，}$$\red{3)(2，}$$\red{2)(2，}$$\red{3)}$

·$\red{3}$只蚂蚁出去有五种组合：$\red{(1，}$$\red{1，}$$\red{2)(1，}$$\red{1，}$$\red{3)(1，}$$\red{2，}$$\red{2)(1，}$$\red{2，}$$\red{3)(2，}$$\red{2，}$$\red{3)}$

·$\red{4}$只蚂蚁出去有三种组合：$\red{(1，}$$\red{2，}$$\red{2，}$$\red{3)(1，}$$\red{1，}$$\red{2，}$$\red{2)(1，}$$\red{1，}$$\red{2，}$$\red{3)}$

·$\red{5}$只蚂蚁出去有一种组合：$\red{(1，}$$\red{1，}$$\red{2，}$$\red{2，}$$\red{3)}$

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

输入格式

第$\red{1}$行：$\red{4}$个用空格隔开的整数$\red{T，}$$\red{A，}$$\red{S，}$$\red{B.}$

第$\red{2}$到$\red{A+1}$行：每行是一个正整数，为某只蚂蚁所在的家族的编号．

输出格式

输出一个整数，表示当$\red{S}$到$\red{B（}$包括$\red{S}$和$\red{B）}$只蚂蚁出去觅食时，不同的组队方案数．

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

样例

输入样例

5 2 3

输出样例

10

提示

样例说明 $\red{2}$只蚂蚁外出有$\red{5}$种组合，$\red{3}$只蚂蚁外出有$\red{5}$种组合．共有$\red{10}$种组合