Subsets Sum

You are given a set of N positive integers (set A). Find the number of subsets that have their sums equal to S.
Subsets may have any number of integers between 1 to N (inclusive).
Note: A set will not consist of repeated elements

Example 1

If A = {1, 2, 5, 10, 12} & S = 12,  
Then subsets are,  
{2, 10} & {12}

Example 2

If A = {1, 2, 3, 4, 5} & S = 5,  
Then subsets are,  
{1, 4}, {2, 3} & {5}

Input Format

First line contains 2 integers, N & S.
Next line contains N space seperated integers(integers of the set A), with the i^th of them being A_i.

Output Format

Number of subsets that have their sums equal to S.

Constraints

• 1 \(\leq\) N, S \(\leq\) 1000
• 1 \(\leq\) A_i \(\leq\) 1000
   

Limits

• Time Limit: 1s
• Memory Limit: 256MB

Sample Input 0

5 12
1 2 5 10 12

Sample Output 0

2

Sample Input 1

5 5
1 2 3 4 5

Sample Output 1

3