Monica is a chef. Today, she wants to create dishes consisting of n ingredients. x grams of ith ingredient has energy xai. Use 00=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) ≤y. Find the sum of energies of all the dishes made by her modulo 109+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, ith of which is equal to ai
Output:
Print only one line containing the sum of energies of all the dishes made by Monica modulo 109+7
Constraints:
-
1≤n≤105
-
0≤ai≤105
-
∑ni=1ai≤105
-
0≤y≤109
There are ten distinct dishes possible with total weight ≤3 :
- 0 grams of ingredient one and 0 grams of ingredient 2. Energy = 0102=0
- 0 grams of ingredient one and p(1≤p≤3) grams of ingredient 2. Energy = 01p2=0
- p(1≤p≤3) grams of ingredient one and 0 grams of ingredient 2. Energy = p102=0
- 1 grams of ingredient one and 1 grams of ingredient 2. Energy = 1112=1
- 1 grams of ingredient one and 2 grams of ingredient 2. Energy = 1122=4
- 2 grams of ingredient one and 1 grams of ingredient 2. Energy = 2112=2
The sum of energies is thus 1+4+2=7
