Dynamic Programming || Python || O(n^2*k)
\n# Complexity\n- Time complexity:\nO(n^2k)\n\n- Space complexity:\nO(n^2k)\n# Code\n\nfrom collections import defaultdict\n\nclass Solution:\n    def sumOfPowe
\n# Complexity\n- Time complexity:\nO(n^2*k)\n\n- Space complexity:\nO(n^2*k)\n# Code\n```\nfrom collections import defaultdict\n\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        mod = 10**9+7\n        ans = 0\n        n = len(nums)\n        dp = [[[None]*(k+1) for _ in range(n+1)] for _ in range(n+1)]\n        \n        def f(idx, count, k):\n            if k <0 or count <0:\n                return 0\n            if dp[idx][count][k] is not None:\n                return dp[idx][count][k]\n            if count == 0 and k != 0:\n                dp[idx][count][k] = 0\n                return 0\n            if k == 0 and count == 0: \n                dp[idx][count][k] = 1\n                return 1\n            if idx == len(nums):\n                return 0\n            \n            ways = 0\n            ways += (f(idx+1, count-1, k-nums[idx]) + f(idx+1, count, k)) % mod\n            dp[idx][count][k] = ways\n            return ways % mod\n        \n        for i in range(1, len(nums)+1):\n            temp_ans = f(0, i, k)\n            ans += pow(2, n-i, mod) * temp_ans\n            ans = ans % mod\n            \n        return ans % mod\n\n```
['Math', 'Dynamic Programming', 'Python3']