python3 2d DP
Time Complexity: O(n^2k)\nSpace Complexity: O(nk)\n\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        # dp[i][k] - how many s
Time Complexity: O(n^2k)\nSpace Complexity: O(nk)\n```\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        # dp[i][k] - how many subsequences with sum of k using i numbers\n        n = len(nums)\n        dp = [[0] * (k+1) for _ in range(n+1)]\n        # base case this is always true\n        dp[0][0] = 1\n        # iterate through each extra number and update the dp array\n        for num in nums:\n            # make a copy of the current array and edit this \n            # because if you don\'t then you can use a number \n            # more than once because you\'ll have the entry \n            # dp[2][2] = 1 for the first test case as you can \n            # have 2 ones that add up to 2 since dp[1][1] will\n            # be edited before dp[2][2]\n            ndp = [dp[i].copy() for i in range(n+1)]\n            for i in range(1,1+n):\n                for j in range(k+1):\n                    if j-num >= 0:\n                        ndp[i][j] += dp[i-1][j-num]\n            dp = ndp\n        \n        # each subsequences contributes 2^(n-i) \n        # as there are i in the subsequence already\n        # and the rest choose to be in it or not \n        ans = 0\n        for i in range(1,n+1):\n            ans += dp[i][k] * pow(2,n-i,int(1e9)+7)\n            ans %= int(1e9)+7\n        return ans\n```
['Dynamic Programming']