Count of Subsets with a Given Sum

Given an integer array \(A = [a_1, a_2, \ldots, a_n]\) and a target integer \(K\), your task is to count the number of subsets of \(A\) whose sum equals \(K\). A subset can be any collection of elements (including the empty subset, which has a sum of 0). Since the answer can be very large, output the count modulo \(10^9+7\).

Note: The empty subset is always counted when \(K = 0\).

inputFormat

The input is provided via stdin and consists of two lines:

• The first line contains two integers \(n\) and \(K\) separated by a space, where \(n\) is the number of elements in the array and \(K\) is the target sum.
• The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer on a new line representing the number of subsets that sum to \(K\), taken modulo \(10^9+7\).

3 6
2 4 6

2