题目描述

选取恰好 $m$ 盆花摆成一排，共有 $n$ 种花，第 $i$ 种最多使用 $a_i$ 盆。同种花连续摆放，各种花按编号从小到大排列。求摆放方案数。

输入格式

第一行 $n,m$。第二行 $n$ 个整数 $a_i$。

输出格式

输出方案数对1000007取模的结果。

样例

2 4
3 2

2

数据范围

$1\le n,m\le100$，$0\le a_i\le100$。