题目描述

Devu有 $\red N$ 个盒子，第 $\red i$ 个盒子中有 $\red{A_i}$ 枝花。

同一个盒子内的花颜色相同，不同盒子内的花颜色不同。 Devu要从这些盒子中选出 $\red M$ 枝花组成一束，求共有多少种方案。

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

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

输入格式

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

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

输出格式

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

样例

输入样例

3 5
1 3 2

输出样例

3

提示

$\red{1\leq N\leq 20}$ ,

$\red{0\leq M\leq 10^{14}}$ ,

$\red{0\leq A_i\leq 10^{12}}$