8 Lines O(kn^2)
\n# Code\npython3 []\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        @cache\n        def rec(idx: int, curr_sum: int, curr_
\n# Code\n```python3 []\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        @cache\n        def rec(idx: int, curr_sum: int, curr_length: int) -> int:\n            if curr_sum == k: return 2**(len(nums)-curr_length)\n            if curr_sum > k or idx == len(nums): return 0\n            return sum((rec(new_idx, curr_sum + nums[new_idx], curr_length + 1)) for new_idx in range(idx+1, len(nums)))\n        return rec(-1, 0, 0) % (10 ** 9 + 7)\n        \n        \n```
['Python3']