TC: O(NK) SC: O(K) | Very Efficient DP
Code\npython3\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        def calc(p: int) -> int:\n            ans, tmp = 1, 2\n      
# Code\n```python3\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        def calc(p: int) -> int:\n            ans, tmp = 1, 2\n            while p:\n                if p & 1:\n                    ans = (ans * tmp) % 1000000007\n                tmp = (tmp * tmp) % 1000000007\n                p >>= 1\n            return ans\n\n        f = [0] * (k + 1)\n        f[0] = calc(len(nums))\n        # Same as calc(1000000007 - 2)\n        inverse = 500000004\n        for num in nums:\n            for i in range(k, num - 1, -1):\n                f[i] = (f[i] + (f[i - num] * inverse) % 1000000007) % 1000000007\n        return f[k]\n```
['Math', 'Dynamic Programming', 'Python3']