题目描述

有 $N$ 种不同颜色的单位立方体积木，颜色编号为 $0,1,\ldots,N-1$。第 $i$ 种颜色共有 $c_i$ 块。

搭建结构时必须使用所有积木。每次放置一块积木时，可以把它放在地面上，或者直接放在某一块已经放置的积木上。因此最终结构由若干竖直的积木塔组成。

还要求：同一种颜色的所有积木必须处于完全相同的高度。

拆除结构时，每一步选择一种颜色，并一次性移除该颜色的所有积木；只有当这些积木上方都没有其他积木时，才能执行这一步。一个颜色排列是合法拆除顺序，当且仅当可以按照该排列依次移除所有颜色。

两个结构被认为是“本质不同”的，当且仅当存在一对颜色 $i,j$，使得在其中一个结构中存在颜色 $i$ 的积木直接放在颜色 $j$ 的积木上，而在另一个结构中不存在这种直接接触关系。

给定各颜色的积木数量，以及两个整数 minWays、maxWays，求合法拆除顺序数量位于 $[minWays,maxWays]$ 内的本质不同结构有多少种。

输入格式

第一行三个整数 $N$、minWays、maxWays。

第二行包含 $N$ 个整数 $c_0,c_1,\ldots,c_{N-1}$，表示各颜色的积木数量。

输出格式

输出一个整数，表示满足条件的本质不同结构数量。

数据范围

• $1\le N\le 6$；
• $1\le c_i\le 7500$；
• $1\le \text{minWays}\le \text{maxWays}\le 720$。

样例 1

输入

3 1 1
2 2 2

输出

6