The special value of sequence of integers is defined as the number of non empty subsequences where the sum of elements is equal to k. Given an array arr of n integers and an integer k. Find the sum of special values of all non empty subsequences of arr. Since the sum can be large. Report it modulo 1e9 + 7.

Constraints:

1 <= N <= 2000

1 <= arr[i] <= 1e9

1 <= k <= 2e12

Example: n = 4, k = 3, arr = [3, 1, 4] ans is 6.

ans = 2(contribution of sequence [1, 4]) + 4(contribution of [4]) = 6

Kindly help me with the above probelm, Thanks. I tried forming dp state based on unique values and for each possible subsequence where sum equals target, 2^(n — currentElementsCount) will be its contribution to ans. However couldn't arrive at a proper solution.

Upd1: changed title, added example