Simple explanation
Intuition\n- If we find a substring that sums to k how many substrings are actually added to our result?\n\n\n\nHere we have index 0 and 1 which sum to our k.\n
# Intuition\n- If we find a substring that sums to *k* how many substrings are *actually* added to our result?\n\n![image.png](https://assets.leetcode.com/users/images/86d1bbff-b32c-4e96-816c-6ef0482066b0_1710611376.4645696.png)\n\nHere we have index 0 and 1 which sum to our k.\nSubarrays that will include both of these values are:\n\n![image.png](https://assets.leetcode.com/users/images/670d3996-8ff2-4c12-b291-d73de24e5a11_1710612130.54281.png)\n\nWhat we are actually doing here is *choosing* every combination of other values in the array\n\n![image.png](https://assets.leetcode.com/users/images/e5abfd98-44d4-4924-8d60-80cd623e7059_1710612234.4965398.png)\n\n- So, aside from the 2 numbers in our combo there are 3 other numbers which we can choose from, *n = 3*.\n    - 1 - the subarray containing only our two numbers\n        - 3 choose 0 = 1\n    - 3 - each of the subarrays containing 1 more number\n        - 3 choose 1 = 3\n    - 3 - each of the subarrays containing 2 more numbers\n        - 3 choose 2 = 3\n    - 1 - the subarray containing all of the numbers\n        - 3 choose 3 = 1\n\n- This sums to 8 subarrays containing this combination, repeat this for every combination.\n\n# Approach\nWe can break this down into two major issues:\n1. How do we find all combinations\n2. How do we calculate total subarrays added by a combination (tackled in intution section)\n3. (bonus) How do we do it and not get TLE\n\n## Find All Combinations:\nWe can perform a DFS to find us all paths which lead to our target *k*.\n\nBecause we only need to know of the lengths of each substring which sums to *k* we don\'t need a specific path, we only need to track how much more our sum needs to equal *k*\n\nWe also need to track how deep we are in path, because this is the \'length\' of our path that will be used to calculate the total number of combinations.\n\nWe can also @cache (or memoize) this function in order to increase efficiency, because all of the inputs are hashable.\n\n## Calculate total subarrays added by a combination\nThe function for n Choose r is:\n```\nfactorial(n) // (factorial(r) * factorial(n - r))\n``` \nWe can call this recursively to efficiently calculate total number of combinations in our range [1, length of nums - length of combination]\n\nWe can also @cache (or memoize) this function in order to increase efficiency, because all of the inputs are hashable.\n\n# Code\n```\nclass Solution:\n    @cache\n    def chooseFromRemaining(self, n , r):\n        if r <= 0:\n                return 0\n        if r == 1:\n            return factorial(n) // (factorial(r) * factorial(n - r))\n        return factorial(n) // (factorial(r) * factorial(n - r)) + self.chooseFromRemaining(n,r-1)\n\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        mod = 10 ** 9 + 7\n        n = len(nums)\n\n        @cache\n        def dfs(start, target, l):\n            if target == 0:\n                ret = self.chooseFromRemaining(n - l, n - l)\n                return ret + 1\n\n            if target < 0:\n                return 0\n\n            ret = 0\n\n            for i in range(start+1, n):\n                ret += dfs(i, target - nums[i], l + 1)\n                ret %= mod\n            return ret\n        \n        ans = 0\n\n        for i in range(n):\n            ans += dfs(i, k - nums[i], 1)\n            ans %= mod\n\n        return ans        \n    \n```
['Python', 'Python3']