All Tracks Algorithms Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?