Subset Sums Revisited

All submissions for this problem are available.
You are given a sequence $A$ of $N$ integers: $(A_1, A_2, \ldots, A_N)$. From this sequence, you create another sequence of size $N$: $B = (B_1, B_2, \ldots, B_N)$, where $B_i = 2^{A_i}$. You are also given an integer $K$. You need to output the number of subsequences of $B$ whose sum is exactly $K$. Since the answer might be huge, output it modulo $10^9+7$. ###Input  The first line contains the number of testcases in file $T$  Each testcase is described as follows:  The first line contains two integers, $N$ and $K$.  The second line contains $N$ space separated integers: $A_1, A_2, \ldots, A_N$ ###Output Output $T$ lines each containing a single integer which should be the answer. ###Constraints  $1 \leq T \leq 200$  $1 \leq N \leq 100$  $0 \leq A_i \leq 60$  $1 \leq K < 2^{61}$ ###Sample Input ``` 1 3 8 2 2 2 ``` ###Sample Output ``` 3 ``` ###Explanation The sequence $A$ is $(2, 2, 2)$. Hence the sequence $B$ is $(4, 4, 4)$. We can pick any two of these to get a sum of 8. Hence the answer is 3.Author:  deadwing97 
Tags  deadwing97 
Date Added:  13122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, kotlin 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions