Find the Sum of the Power of All Subsequences
You are given an integer array nums of length n and a positive integer k.
The power of an array of integers is defined as the number of subsequences with their sum equal to k.
Return the sum of power of all subsequences of nums.
Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
nums = [1,2,3], k = 3Output
6There are five subsequences of
nums with non-zero power, and their powers sum to 2 + 1 + 1 + 1 + 1 = 6.Example 2
Input
nums = [2,3,3], k = 5Output
4There are three subsequences of
nums with non-zero power, and their powers sum to 2 + 1 + 1 = 4.Constraints
- 1 <= n <= 100
- 1 <= nums[i] <= 10^4
- 1 <= k <= 100