SOLVE
LATER
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\).
You can check all \(2^N\) possibilites:
AAA -> Bad
AAB -> Good
ABA -> Good
ABB -> Bad
BAA -> Bad
BAB -> Good
BBA -> Good
BBB -> Bad