214. Devu和鲜花

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例:

3 5
1 3 2

输出样例:

3