Question
Magical Treasures and the Number K
You have n treasures, each with a certain preciousness value denoted by the integer array nums. You are also given a magical number k.
Your task is to find the number of different subsets of treasures such that the total preciousness of the chosen treasures is exactly equal to k.
Since the number of ways can be very large, return the answer modulo 10⁹ + 7.
Input
The first line contains two integers, n and k, representing the number of treasures and the magical number.
The second line contains n space-separated integers — the preciousness values of the treasures.
The second line contains n space-separated integers — the preciousness values of the treasures.
Output
Print a single integer — the number of subsets whose total preciousness equals k.
Example
Sample Input
4 5
1 4 4 5
Sample Output:
3
Explanation
The possible ways are:
[1, 4]
[1, 4]
[5]
Hence the output will be 3.
4 5
1 4 4 5
Sample Output:
3
Explanation
The possible ways are:
[1, 4]
[1, 4]
[5]
Hence the output will be 3.