题目描述

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

如果一共有${S，}$${S+1...，}$${B(1≤}$${S≤}$${B≤}$${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}$行：${4}$个用空格隔开的整数${T，}$${A，}$${S，}$${B.}$

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

输出格式

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

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

样例

输入样例

5 2 3

输出样例

10

提示

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