Java DP Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\nclass Solution {\n    final long mod = (int)1e9 + 7;\n    Map<String, Long> memo = new HashMap<>();\n    Map<Integer, Long> memo2 = new HashMap<>();\n\n    public long pow(int x, int n) {\n        if (n == 0) {\n            return 1;\n        }\n\n        if (n == 1) {\n            return x;\n        }\n\n        if (memo2.containsKey(n)) {\n            return memo2.get(n);\n        }\n\n        long ans;\n\n        if ((n & 1) == 0) {\n            ans = (((long)pow(x, n / 2) % mod) * ((long)pow(x, n / 2) % mod) % mod);\n        } else {\n            ans = ((((long)pow(x, n / 2) % mod) * ((long)pow(x, n / 2) % mod) % mod) * x % mod);\n        }\n\n        memo2.put(n, ans);\n        return ans;\n    }\n\n    public long helper(int[] nums, int k, int i, long sum, int n, int len) {\n        if (i == n) {\n            if (sum == k) {\n                return pow(2, n - len);\n            }\n            return 0;\n        }\n\n        String key = i + " " + sum + " " + len;\n        if (memo.containsKey(key)) {\n            return memo.get(key);\n        }\n\n        long take = 0;\n        if (sum + nums[i] <= k) {\n            take = helper(nums, k, i + 1, sum + nums[i], n, len + 1);\n        }\n\n        long notTake = helper(nums, k, i + 1, sum, n, len);\n\n        memo.put(key, (take % mod + notTake % mod) % mod);\n        return memo.get(key);\n    }\n\n    public int sumOfPower(int[] nums, int k) {\n        memo.clear();\n        return (int)helper(nums, k, 0, 0, nums.length, 0);\n    }\n}\n```
['Java']