Monica is a chef. Today, she wants to create dishes consisting of n ingredients. x grams of \(i^{\text{th}}\) ingredient has energy \(x^{a_i}\). Use \(0 ^ 0 = 1\). Two dishes are different if the amount of an ingredient differs in them. The energy of a dish is equal to product of energies of individual ingredients. Also, each dish is to be packed in a different container which can afford a weight of upto y grams.
She makes all distinct dishes with weight(= sum of amounts of ingredients) \( \le y\). Find the sum of energies of all the dishes made by her modulo \(10^9 + 7\). Note that an empty dish(one in which all ingredients have amount 0) is also valid.
Input:
The input consists of two lines:
- The first line contains two integers, n and y
- The second line contains n space separated integers, \(i^{\text{th}} \) of which is equal to \(a_i\)
Output:
Print only one line containing the sum of energies of all the dishes made by Monica modulo \(10^9 + 7\)
Constraints:
-
\(1 \le n \le 10^5\)
-
\(0 \le a_i \le 10^5\)
-
\( \sum_{i=1}^{n} a_i \le 10^5 \)
-
\(0 \le y \le 10^9\)
2 3 1 2
7
There are ten distinct dishes possible with total weight \( \le 3\) :
- 0 grams of ingredient one and 0 grams of ingredient 2. Energy = \(0^1 0^2 = 0\)
- 0 grams of ingredient one and \(p(1 \le p \le 3)\) grams of ingredient 2. Energy = \(0^1 p^2 = 0\)
- \(p(1 \le p \le 3)\) grams of ingredient one and 0 grams of ingredient 2. Energy = \(p^1 0^2 = 0\)
- 1 grams of ingredient one and 1 grams of ingredient 2. Energy = \(1^1 1^2 = 1\)
- 1 grams of ingredient one and 2 grams of ingredient 2. Energy = \(1^1 2^2 = 4\)
- 2 grams of ingredient one and 1 grams of ingredient 2. Energy = \(2^1 1^2 = 2\)
The sum of energies is thus \(1 + 4 + 2 =7\)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor