该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

​唉，出题好难啊登登心想，有太多种类的题目可以选择，现在登登要出 $m$ 道题,但一共有 $n$ 种类型的题目，从 $1$ 到 $n$ 标号，为了使题目种类丰富，规定第 $i$ 种题不能出超过$a_i$ ，出题时同一种题放在一起，且不同种类的题需按标号的从小到大的顺序依次摆列。

输入格式

​第一行包含两个正整数 $n$ 和 $m$ ，中间用一个空格隔开。第二行有 $n$ 个整数，每个整数之间用一个空格隔开表示 $a_i。$$0<n\le 100,0<m\le100,0<a_i\le100$

输出格式

输出一个整数表示方案数。方案数可能比较多，需要对 $10^{6}+7$ 取模​

输入样例

2 4
3 2

输出样例

2