A 0-1 knaps problem
Intuitiondp(i,target,length) means If we want to find a sub-sequence, which sum(sub-sequence)=k, and its length = $length$,How many ways we can use? A 0-1 knaps
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
$dp(i,target,length)$ means `If we want to find a sub-sequence, which sum(sub-sequence)=k, and its length = $length$,How many ways we can use`? A 0-1 knaps problem, If we have nothing to choose, then we get 1 if target is 0 and length is 0
$$ dp(i,target,length)=dp(i-1,target,length)+dp(i-1,target-nums[i],length-1) $$
According to them, we write a TLE code
```python3 []
class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        @cache
        def dfs(i: int, target: int, length: int) -> int:
            if i < 0:
                return 1 if target == 0 and length == 0 else 0
            res = dfs(i - 1, target, length)
            if target >= nums[i]:
                res = (res + dfs(i - 1, target - nums[i], length - 1)) % MOD
            return res
        
        ans = 0
        n = len(nums)

        for length in range(1, n + 1):
            ans = (ans + pow(2, n - length, MOD) * dfs(n - 1, k, length)) % MOD
            dfs.cache_clear()
        return ans
```
# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(k + 1, vector<long long>(n + 1, 0)));
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int target = 0; target <= k; target++) {
                for (int length = 0; length <= n; length++) {
                    dp[i][target][length] = dp[i - 1][target][length];
                    if (target >= nums[i - 1] && length > 0) {
                        dp[i][target][length] = (dp[i][target][length] + dp[i - 1][target - nums[i - 1]][length - 1]) % MOD;
                    }
                }
            }
        }
        vector<long long> powersOfTwo(n + 1, 1);

        for (int i = 1; i <= n; i++) {
            powersOfTwo[i] = (powersOfTwo[i - 1] * 2) % MOD;
        }
        long long ans = 0;
        for (int length = 1; length <= n; length++) {
            ans = (ans + powersOfTwo[n - length] * dp[n][k][length]) % MOD;
        }
        return ans;
    }
};
```
```python3 []
class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        @cache
        def dfs(i: int, target: int, length: int) -> int:
            if i < 0:
                return 1 if target == 0 and length == 0 else 0
            res = dfs(i - 1, target, length)
            if target >= nums[i]:
                res = (res + dfs(i - 1, target - nums[i], length - 1)) % MOD
            return res
        
        ans = 0
        n = len(nums)

        for length in range(1, n + 1):
            ans = (ans + pow(2, n - length, MOD) * dfs(n - 1, k, length)) % MOD
            dfs.cache_clear()
        return ans
```
['Dynamic Programming', 'Memoization', 'C++', 'Python3']