Python Hard
\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        \'\'\'\n        nums[i] is positive\n        k is only 100\n        n is o
```\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        \'\'\'\n        nums[i] is positive\n        k is only 100\n        n is only 100, so n ** 3 works\n        \n        initital "feeling" was dp\n        \n        how many combinations sum to k in nums?: say, n combinations\n        \n        for each subsequence, how many of the n combinations can be form?\n        \n        big bitmask with i << 100?\n        \n        order of nums doesnt matter\n        \n        say you get some combination of n nums that sum to k\n        \n        how many subsequences "engulf" this combination\n        N - n "other" numbers\n        \'\'\'\n        MOD = 10 ** 9 + 7\n        N = len(nums)\n        nums.sort()\n        \n        @cache\n        def calc(index, k, n):\n            if k == 0:\n                return (2 ** (N - n)) % MOD\n                \n            if index == N or k < 0:\n                return 0\n        \n            return (calc(index + 1, k, n) + calc(index + 1, k - nums[index], n + 1)) % MOD\n        \n        return calc(0, k, 0) % MOD\n        \n```
['Python3']