题目描述

Devu 有 $N$ 个盒子，第 $i$ 个盒子中有 $A_i$ 枝花。

同一个盒子内的花颜色相同，不同盒子内的花颜色不同。

Devu 要从这些盒子中选出 $M$ 枝花组成一束，求共有多少种方案。

若两束花每种颜色的花的数量都相同，则认为这两束花是相同的方案。

结果需对 $10^9+7$ 取模之后方可输出。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个空格隔开的整数，表示 $A_1,A_2,\dots,A_N$。

输出格式

输出一个整数，表示方案数量对 $10^9+7$ 取模后的结果。

样例

输入样例：

3 5
1 3 2

输出样例：

3

样例解释

三个盒子分别有花数量：1, 3, 2。

要选出 5 枝花，可能的方案（每种颜色的花的数量）：

1. 从第1个盒子取 1 枝，第2个盒子取 3 枝，第3个盒子取 1 枝 → 1+3+1=5
2. 从第1个盒子取 1 枝，第2个盒子取 2 枝，第3个盒子取 2 枝 → 1+2+2=5
3. 从第2个盒子取 3 枝，第3个盒子取 2 枝 → 0+3+2=5

共 3 种方案。

数据范围

• $1 \le N \le 20$
• $0 \le M \le 10^{14}$
• $0 \le A_i \le 10^{12}$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB