小柒分糖果
题号：NC288867
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小柒作为班主任，最近为自己班的学生购买了 n 种糖果，第 i 种糖果有 a_i 颗。班级里一共有 m 名学生，小柒可以决定每种糖果发几颗，发给哪几名学生，每名学生获得的糖果数量。
\hspace{15pt}小柒想知道他一共有多少种发糖果的方法。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
\hspace{15pt}如果两种发糖果的方法中，有任何一名学生得到的某种糖果数量不同，则认为这两种方法不同。

输入描述:

\hspace{15pt}第一行输入两个整数 n,m\left(1\leq n,m\leq 10^5\right) 代表糖果的种类数、班级的人数。 
\hspace{15pt}第二行输入 n 个正整数 a_1,a_2,\dots,a_n\left(1\leq a_i\leq 10^5\right) 代表每种糖果的数量。

输出描述:

\hspace{15pt}输出一个整数代表小柒一共有多少种发糖果的方法。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

复制 
3 1
1 1 1

输出

复制 
8

说明

\hspace{15pt}在这个样例中，仅有一名学生。一共有八种不同的方案，依次为：
\hspace{23pt}\bullet\,什么糖果都不发给他；
\hspace{23pt}\bullet\,发给他一颗第 1 种糖果；
\hspace{23pt}\bullet\,发给他一颗第 2 种糖果；
\hspace{23pt}\bullet\,发给他一颗第 3 种糖果；
\hspace{23pt}\bullet\,发给他一颗第 1 种糖果和第 2 种糖果；
\hspace{23pt}\bullet\,发给他一颗第 1 种糖果和第 3 种糖果；
\hspace{23pt}\bullet\,发给他一颗第 2 种糖果和第 3 种糖果；
\hspace{23pt}\bullet\,发给他一颗第 1 种糖果、第 2 种糖果和第 3 种糖果。
示例2

输入

复制 
5 5
12 34 12 3 1

输出

复制 
88875699