题目描述

班主任小柒为班级 $m$ 名学生购买了 $n$ 种糖果，其中第 $i$ 种糖果有 $a_i$ 颗。小柒需决定每种糖果发放的数量以及发给哪些学生。若两种发糖果方式中，有任意一名学生得到的某种糖果数量不同，则视为不同的发糖果方法。小柒想知道总共有多少种发糖果的方法，由于答案可能很大，需将结果对 $(10^9 + 7)$ 取模后输出。

输入格式

• 第一行输入两个整数 $n$、$m$（$1 \leq n, m \leq 10^5$ ），分别表示糖果的种类数和班级的学生人数。
• 第二行输入 $n$ 个正整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq 10^5$ ），代表每种糖果的数量。

输出格式

输出一个整数，为小柒发糖果方法的数量对 $(10^9 + 7)$ 取模后的结果。

示例

输入

3 1
1 1 1

输出

8