D. Subset Sums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp has an array $$$a$$$ that consists of $$$a_1,a_2,\cdots, a_n$$$. How many unique subsets of $$$a$$$ sum to $$$k$$$? Print your answer in mod $$$10^9+7$$$.

Here, subsets are distinguished by the indices used to create those subsets.

Input

The first line of input contains $$$n$$$ and $$$k$$$ $$$(1\le n\le 5\cdot 10^5, 0\le k\le 10^9)$$$.

The second line of input contains $$$a_1,a_2,\cdots,a_n$$$ $$$(0\le a_i\le 10^9)$$$.

Output

Output the answer in mod $$$10^9+7$$$.

Example
Input
5 3
8 1 3 2 4
Output
2
Note

In this testcase, only the sets $$$\{1,2\}$$$ and $$$\{3\}$$$ work. These sets have a sum of $$$3$$$, as desired. The sets are unique since they are composed of different sets of indices.

$$$$$$\color{white}{y=\frac{1}{\max(b,1+b-a)}x\{0\le y\le 2\}}$$$$$$ $$$$$$\color{white}{y=-\frac{1}{1+b-a}x+\frac{2}{1+b-a}\cdot\frac{\sqrt{2-a}}{\sqrt{2-a}}\{0\le y\le 2\}}$$$$$$ $$$$$$\color{white}{y=-\sqrt{a-1+b}\,x+a-1\{0\le x\le 2\}\{-2\sqrt{b}\le y\le 1\}}$$$$$$ $$$$$$\color{white}{x=-\frac{1}{\min(b+a-1,0.25)}\left(y-2.5+\frac{a}{2}\right)^2-a+3\{0\le x\le 2\}\{1\le y\le 2\}}$$$$$$ $$$$$$\color{white}{b=10^{-6}}$$$$$$