题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

3 5
1 3 2

3

数据范围

• $1≤N≤20$
• $0≤M≤10^14$
• $0≤A_i≤10^12$

来源

• CF451E
• 算法竞赛进阶指南