Closing Ceremony at Lolympics
Tag(s):

## Algorithms, Dynamic Programming, Medium, Simple-math

Problem
Editorial
Analytics

Lolympics is over! Talented Tanmay and Pretty Parmita have made their country proud by winning $N$ medals combined. That's a great achievement, considering it's their first time at the Lolympics. Getting bored during the closing ceremony, they decided to make a game out of the medals they have won.

Both Tanmay and Parmita have a big bag. They gave the $i^{th}$ medal a value $A_i$. Now they want to count the number of ways in which they can put each medal into either of the bags such that the sum of value of medals in each bag is greater than equal to the magic number $K$. Both of them come up with different answers and hence they look forward to you to help them out with the correct answer. Can you live up to their expectations ?

Constraints :

$1 \le N \le 10^3$
$1 \le A_i \le 10^6$
$1 \le K \le 10^5$

Input Format :

The first line contains $N$ and $K$. The next line contains $N$ spaces separated integers, the $i^{th}$ integer denotes $A_i$.

Output Format :

Output the number of ways in which Tanmay and Parmita can partition the medals in the two bags. Since the value can be huge, output it modulo $10^9 + 7$.

SAMPLE INPUT
3 10
5 12 11
SAMPLE OUTPUT
4
Explanation

You can check all $2^N$ possibilites:
AAB -> Good
ABA -> Good
BAB -> Good
BBA -> Good

Time Limit: 2.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: 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, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

October Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Math > Number Theory
• Data Structures > Advanced Data Structures
• Math > Probablity
• Algorithms > Graphs