Powerful dishes
Tag(s):

## Algorithms, Binomial Coefficients, Eulerian number, Fast Fourier transform, Generating Functions, Hard, Stirling Numbers

Problem
Editorial
Analytics

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$

SAMPLE INPUT
2 3
1 2
SAMPLE OUTPUT
7
Explanation

There are ten distinct dishes possible with total weight $\le 3$ :

1. 0 grams of ingredient one and 0 grams of ingredient 2. Energy = $0^1 0^2 = 0$
2. 0 grams of ingredient one and $p(1 \le p \le 3)$ grams of ingredient 2. Energy = $0^1 p^2 = 0$
3. $p(1 \le p \le 3)$ grams of ingredient one and 0 grams of ingredient 2. Energy = $p^1 0^2 = 0$
4. 1 grams of ingredient one and 1 grams of ingredient 2. Energy = $1^1 1^2 = 1$
5. 1 grams of ingredient one and 2 grams of ingredient 2. Energy = $1^1 2^2 = 4$
6. 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$

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Math > Combinatorics