No submission language available for this problem.

Background

无限的宇宙，无限的可能。时空管理员 A 在某个命名为无限的宇宙中发现了许多种带有特殊能量的宝石，由于数量过于巨大，他暂时将这些宝石称为无限宝石。这些宝石能量所具有的的能力极具诱惑力，A 他可能抵抗不了，摸了摸口袋中的能量隔绝手套，准备偷偷地拿走一些。

Description

A 的能量手套是消耗品，每次拿一个宝石，手套的耐久力就会消耗一部分，该部分数值与宝石能量等值。当手套的耐久力为 0 时，便无法再获取宝石。

现在在 A 面前有 n 种不同的无限宝石，种类 i 宝石带有能量 a_i 。能量手套的总耐久为 m ，A 想知道，他能有多少种获得宝石的策略。注意，不拿也是一种策略。

结果可能非常巨大，需要对 100000007 取模

Format

Input

第一行两个整数 n，m 分别表示无限宝石的种数，和手套耐久值。

第二行 n 个整数，分别表示这多种无限宝石的能量值。

Output

一个整数，表示 A 获取无限宝石的方案总数。

Samples

3 10
3 3 11

10

Limitation

保证 $60\%$ $1 \leq n \le 10^3$

对于 $100\%$ 的数据

$1 \leq n \le 10^4$

$1 \leq m \leq 10^4$

$1\leq a_i \leq 10^9$